Are there any heatsinks or thermal paste or something that people have used successfully?
Have you looked at the regulator device on your Mega board? It's a SMD mounted device that gets it's heat sinking via it's pin and underside. I can't see any way you can effectively increase it's heat dissipation other then by just lowering the external power voltage to just above it's regulation drop out specification. If you still require more current then that, use an external power supply for your loads.
Lefty