I cleaned the MAF already, using contact cleaner. MAF cleaner is unfortunately not available here. I also cleaned the throttle body with carb cleaner, and changed the spark plugs. It helped a little, at least related to the bad idle, but not regarding power loss.

The whole story is very strange.
I got the car, all was perfect, lots of power, transmission shift smooth.
The only issue I had was the hard starting when the engine is hot.
I got a new CPS, and a mechanics installed it. At that same moment, the transmission shifted very hard.
What happened was that the mechanics has the vacuum line going to the transmission between the housing and the CPS and squeezed the line.
It took me a week to figure that out (he wanted to rebuild the transmission!).
So I told him to remove the CPS, plug a new line, and screw it all together.
He did, then adjusted here and there a little, and the result is, no power, rough idle, strange shifting behavior etc.
Now, weeks later, I still could not solve the issues. I have no idea what he could have done to cause such symptoms.
Of course, he want money, now he told me to "reset" the car to default via his Star Diagnosis, and want another $80 for that.