I have a M104 in my 1996 C36. It is running perfectly (touch wood!).
With the car stationary, it is not possible to exceed 4000 RPM in P, N or D. When the car is moving at say 10 km/h or faster, the engine will rev all the way to the red-line (6400 or so). I believe that this is as designed and is normal.
It would appear that the EMU needs a VSS signal to allow full RPM. Possible problem area?
Secondly, if you suspect a cam sensor problem, disconnect the cam sensor cable and try a run. If there is no change, you might have hit the problem.
Thirdly, I recently had a problem with my 2000 CLK320 M112 engine. It lost significant power above 4000 RPM and accelerated very very very slowly towards max RPM. Cleaning the MAF improved performance a bit. Replacing the MAF restored heroic performance to as new condition!