You wouldn't have problems with regulated HPA in a GBB. The amount of air required to get a paintball moving 300fps is massive compared to the air it would take to fling a bb at 550fps. Most paintball regulators can bring air down sub 200psi and up to about 800psi and hold it there consistently with a paintball gun cycling in the mid 20BPS range.
Why would you believe you would see freeze ups and bleed down from nitrogen(commonly called HPA in the paintball community....)? nitrogen really does not cool off significantly unless MASSIVE quantities are being released.
I would think converting the gun would be as simple as installing a 1/8 NPT fitting into one of the mags gas chamber and running an on-tank or inline regulator. It should be reasonably simple.
If one of you would like a hand with parts selection on the paintball end, I'm actually a qualified airsmith

.