Generally speaking, we can compress air more than we can compress a comparable spring. From pV = nRT = K constant at a fixed temperature T as V --> v (the volume of air is compressed), where v < V, p --> P (the pressure goes up), where P > p, to maintain the constant RHS of the equation.
Thus, the force on the projectile is F = PA = KA/v upon release giving the projectile a = F/m = PA/m = KA/mv acceleration off the muzzle. As we can see, we get more acceleration for more compression to v.
Similarly F = k dX is the force on the same projectile m; so that a = F/m = k dX/m; where k is the spring constant and dX is the compression. Set the two accelerations equal so that KA/mv = k dX/m. Then we have KA/v = k dX and KA/kv = dX if the spring and the compressed gun are to have the same muzzle acceleration.
And now we are beginning to see why the spring has limits the compressed air does not. A spring can only be compressed so far, depending on the diameter of wire in the coil. Gas, when compressed from V --> v can be compressed considerably more v = (1/100) V is not uncommon. But dX = 1/2 X is about the limit for an uncmpressed spring of length X.
The bottom line is that air can be compressed relatively more than a spring so that air has relatively more potential energy than a comparable compressed spring. Of course, one can gin up a small air gun vs a very large spring and the spring would win, but it would not be a comparable spring...not a fair fight in this case.