Carbon Build up on the valves and the exhaust is very common for any old engine no matter how you maintain it , its the by product of the combustion of gasoline.
Issues due to carbon build-up on the valves:
Clogs the valves thus allowing less fuel/air to get inside the cylinder thus reducing power and efficiency of the vehicle.
The above point can cause an uneven power stroke causing engine knock.
Since fuel is not properly burned it will increase the emissions and might fail pollution test.
The EGR or Exhaust Gas Recirculation will now be sending the bad exhaust into the engine. increasing the carbon build up further.
However carbon buildup is not something which affects only one parameter of a car, it can affect the air/fuel intake.
Abstracts from here shows it affects additional parameters
The carbon contributes to abnormal combustion in several ways, but the most dramatic effect in a modern fuel injected engine is the "sponge effect". As the fuel mixture in the cylinder is compressed, the carbon has a tendency to absorb both oxygen and fuel. Once the ignition spark fires, the flame front normally spreads through the chamber, consuming the fuel and air, however, the carbon has a tendency to extinguish the flame front and stifle combustion.
This, combined with the fuel and air that was absorbed, results in poor efficiency. As the chamber decompresses during the exhaust portion of the stroke, the unburned fuel and air is released, resulting in both excessive fuel and air (containing oxygen) entering the exhaust system. The O2 sensor detects the excessive oxygen and the vehicle computer (ECM, ECU, PCM) compensates for this by enriching the mixture.