Any kind of automotive paint will be fine, as long as it's in a can form, also make sure you get some primer too.
I think paint adds a layer of insulation between the copper/aluminium and therefor limits the heat exchange. The more insulation you have, the warmer the copper/aluminium remains, and the less it cools. NOTE: I have no proof about this, but logic tells me this
I too think it will affect the heat exchange, but if you can find 'thermally conductive paint' it wont be an issue.
Just don't paint the fins if you want to keep normal performance. Painting the outside isn't a problem.
If you add any sort of insulating layer to the radiator, it will affect performance; painting the fins will inhibit the transfer of energy from the metal of the radiator to the air. As mentioned above, you will have to use thermally conductive paint or just not paint the fins. I believe that it's anodised initially rather than painted - the oxide layer deposited by the process has similar conductivity to the metal itself. I reckon that you could probably have it anodised again if you removed the existing deposits, but that's probably a lot more trouble than it's worth.
Originaly they are either, electrostackly painted or powder coated. Painting the fins will change the heat exchange properties, because it does add a little coat of paint and may block some fins up, but thats if your really spraying a lot of paint. Just make shure you lightly sand the surface you want to paint, and use light coats near the fins, (only one coat should do it there). You will be fine
If you could find some acid that won't damage the aluminum or copper you could probably burn the paint off. It would be cool just to paint the shroud so do it.