The exercise mats don't specify what they're made out of, but if they are EVA, they should be fine. (EVA is a denser foam, and forms and sands nicely) at any rate they are probably too thick.
You will need to seal the foam before painting, most builders are using "plasti-dip" spray to seal it, but a watered down solution of elmer's glue can work also. After you seal it, you can use just about any spray paint.
As with any project, it's always best to test the glue, sealant & paint on scrap material, just to make sure the materials you have slelected will work together.