Yah, it would basically destroy the cooling abilities. The only exception would to have it professionally anodized. But even then, your going to loose some cooling.
I"m pretty sure that you could. BUT it's all depends on the type of paint that you uses. Definitly have to be spray paint. ExampleExampleExampleExample
There are many other color heatsinks out there if you googled. If you have a spare heatsink, give it a try. First test the temp without the painted coating and one with the painted coating. I'm curious to know the results.