just keep watching tuts an look at something that you want to make an work your way to it.
I moved onto Photoshop after paint, but I really wish I'd started learning Illustrator before now (I've just started teaching myself); It's nice using vector images since theyre always clean[illustrator]. And since the two programs are compatible its worth while to try learn both as you go[Photoshop and Illustrator].
I dont have much experience with C4D but if you have time then you might as well try learn it from youtube tuts. Its quite powerful.
A few options to become familiar with in Photoshop:
-Layer options; try playing around with all those- get here by double clicking on the layer.
-Edit>Free Transform / Transform
-Filter>filter gallery, for different effects
-The clone stamp tool, to cover things up
-The pen tool, for smooth lines
-dodge/burn, to lighten and darken