You should be fine using Krylon Fusion. I recently painted all my filter intakes, and spray bars with this. Just let it air dry for the full 7 days and it will be safe. When looking for the Krylon I had a bit of a hard time finding black as every store just had these crazy designer colurs like Mullberry, Avacado, Camo, Mint Tea and others. Make sure it is the Fusion line though because Krylon make a lot of different types of spray paint.
For pleco caves, Kens fish has some nice pleco caves on his site that I want to try. For now though, I needed something large so I soaked 2 large terra cotta planters in water for a few days, then scored a line around the lenght. I took a screwdriver and hammer and was able to break the pots along the line all the way around. Then for the bottom, I just took pliers and broke that off. Layers all 4 pieces on top of each other, and now I never see the pleco so I guess he's happy. I tried PVC but just didn't like it.