Technically, yes it is possible that the paint could cause an unbalance. In practice, I've found that if you are careful with your painting it works just fine. I am a huge silence freak and after trying some 30+ different kinds of fans I finally broke down and started using ugly noctuas. On my now spare PC (built maybe 5 years ago?) I was going for a green/black thing, so I decided to try painting a fan just to see if it would have any affect on noise. Paint will not "tend to puddle" if you go in light coats. The paint had Zero effect on the noise. No vibration, no extra motor noise, nothing. I'm not sure what effect the smoother painted surface has on the airflow, but I suspect very little if any.
The first fan I painted was an S12 and I took a few pics while doing it. I've painted several P12s, some cheap nexus's, and some gentle typhoons since. Some fans have an E clip or circlip under the sticker, some you just have to push the blades/hub away from the frame (carefully!) There are vids on youtube on how to do this. I wished I had some matte black when I did this one, but I only had gloss kicking around. Florescent green, then UV active green over top on the blades. ~4 extremely light coats on everything.