What type of magnets are you using. If it's your standard fridge magnets, they will not be strong enough to hold whatever you are connecting to. Rare earth magnets are your best bet. I've seen magnets glued into place with both hot glue or contact cement. Just make sure glue has set and is holding magnet nicely. There is a risk of tearing magnets out of foam when pulling the magnets apart. Try covering one magnet with 2mm craft foam to help keep this from happening.
As for paint, do it after magnets are installed. Wouldn't want to wreck a beautiful paint job by cutting divots into you armour and weapons.
Well that's fine. I made a foam gunfighter magnum and it worked out fine. If you already glued it together you could dermal a hole or cut the clue back away, and glue the magnets into the hole made there. Then glue it back, and cover it up with foam putty or quick seal. You just have to mess around