How can gravitational potential energy be stored in empty space?

You're right: potential energy, as taught in introductory physics courses, is a "cheat".

On a fundamental level, there's no such thing -- there's only energy stored in fields. Since field descriptions are more complicated, your course glossed over it by calling the field energy "potential energy". It's totally fine for solving problems, since the bookkeeping is the same, but it can be confusing if you ask where the energy actually is. This is a big logical hole in intro courses.

In your case, the energy is stored in the gravitational field between the two objects. It's totally analogous to how energy is stored in the electric field between two charges. Here, the gravitational field is the metric tensor $g_{munu}$ and the presence of the masses perturbs it from the flat metric $eta_{munu}$.

This gravitational field is not "nothing", even if there are no matter particles there. Its value, energy density, momentum density, etc. can all be measured and observed. In fact, from a modern perspective, there are only fields. Even the rock in your example is just a complicated excitation of the electron, quark, gluon, etc. quantum fields.

Gravitational Potential Energy is the difference in the total energy of a mass between two points in space as a direct consequence of the difference in the length of a metre between the two locations.

In other words, it is a direct result of gravitational length contraction.

The total energy of a mass can be expressed as $$E=mc^2$$

But it is also Force × Distance I.e. it's the distance that a 1N force can be applied by the mass if all of its energy is released..

During free fall, the unit of distance decreases at a rate of $$g/c^2$$ wrt distance fallen.

Therefore the total energy of a mass reduces at a rate of $$mc^2g/c^2$$ Or $$mg$$ wrt distance fallen due to gravitational length contraction.

The change in total energy over a given change in height, mgh (or more generally over a given change in gravitational potential) is what we call Gravitational Potential Energy.

Gravitational length contraction is the result of a reduction in the wavelength of light between the two locations.