Don't worry about nitrogen. Just get it filled with compressed air. That is what most shops do, anyway. 99% of all paintball shops should do it.

And in my experience, scuba shops won't be able to fill to 4500 psi and most also require you to be a certified diver to fill any tanks.