I would say that no, without something slightly more powerful than Paint, there is no simple way to do this without 500 different images.
With something better than Paint, it is easy enough to take that map, use the fill tool, fill in a state, then erase all the other lines on the map. Set the matte to transparent and leave the image size and you should have a layer with just one state filled in. I would assume that it shouldn't be too hard to layer these images on top of each other to create a map with multiple states filled in. I would guess that it would be more difficult to find the x and y coordinates of each image then it would be to create 50 full sized images, but using coordinates would not require loading 50 large images, so its a bit of a tradeoff there.
I would suggest you find some type of software that lets you make the background transparent, because that is all you need. There might actually be a way to do it in Paint, but I don't think so. Other than that, there should be some free software out there that has that capability. We aren't talking serious image manipulation here, what you need should be pretty easy to produce.