It really doesn't matter what you use to make the textures...lol
However, I can't see paint having alot of options that are really needed to make quality textures. You can download the free software suggested or you can get a free 30 day trail of Photoshop from adobe.com. At least you can try it and when you make HL2 textures you can get the photoshop plug-in and save directly as texture. No need for any kind of manual conversion.
I don't think the signs are necessarily all that bad; I just think they are perhaps a little out of scale with everything else.