For the Spring
I know the answer for a compressed spring. The compressed spring has higher mass than the uncompressed spring. The stored energy in a compressed spring shows up as somewhat higher electric fields, overall, between the atoms of the spring.
To minimize confusion, consider a small bar of metal made of a single crystal of aluminum atoms. In the crystal, the nuclei and electron clouds of the atoms configure themselves to a lowest energy configuration. The details of this are complex, but for this example we just need to accept that the atoms wind up at a spacing from each other where if they were closer together they would be repelling each other because (primarily) of the positive charges on the nuclei pushing against each other, and if they were further apart they would be pulling towards each other, primarily because the electron cloud of each atom is distorted to attract the positive nucleus of the neighboring atom.
SO now consider compression. We push on the ends of the bar, forcing the atoms of metal to be somewhat closer to each other then in their relaxed state. The atoms push back, and they do it by the extra electrostatic repulsion of the positively charged nuclei. But when you push those nuclei closer to each other you are increasing the net electric field between them.
Electric fields store energy. The energy density of an electric field is proportional to field-strength squared. So the compressed metal, with somewhat higher electric fields because its positively charged ions are closer together than in relaxed state, has its compression energy stored in the higher electric fields!
BUt of course by relativity, that energy density of an electric field means the electric field has mass density $m=E/c^2$.
So the answer for the compressed spring is that in compression, interatomic electric fields are slightly higher than when the spring is relaxed, and the energy of that slightly higher field is the energy that can be recovered by decompressing that spring, and that higher electric field has a mass from its energy density due to relativity. So a compressed spring weighs more than an uncompressed spring because of the mass of its slightly higher interatomic electric fields.
Unfortunately, I can find no reference to someone measuring the mass difference of a compressed spring and an uncompressed spring. The mass of electric and magnetic fields is indirectly verified by the gravitational red-shift or blue-shift of radio waves. This is verified, oscillators on satellites are measured at higher frequency on the earth's surface, and the reason is that as the radio energy goes down to earth it is increased in energy by the earth's gravitational pull on the mass of its electric and magnetic fields. The energy of a quantum of radiation, a photon, is $hf$ where $h$ is Planck's constant and $f$ is the frequency of the radio. The increase in the frequency of the radio wave as it gets to the earth's surface is exactly consistent with the $mgh$ energy of a "falling" photon from satellite height $h$, photon mass of $hf/c^2$, in gravitational pull $g$.
For the Gravitational Potential
Just as the compressed spring has higher electrostatic field in compression than relaxed, moving a small mass away from the earth increases the net gravitational field found by summing the gravitational field of the earth with the gravitational field of the object being raised. Fields add linearly: linear superposition is the solution of the net gravitational field of two objects. But the energy density in the field proportional to field strength squared. So the field configuration with the objects slightly further apart has more energy in it, found by integrating the energy density over space.
Without actually proving it or having been told it authoritatively by someone who did the math, I will assert by analogy with the spring case that this gravitational field energy density must balance, must account for, the higher potential energy of the mass lifted higher above the earth. This would then suggest that the weight of the object when it is at higher height is the same as when it is on the ground, because the extra energy, the potential energy, is not physically located in the object lifted, but in the gravitational field around and in between the object and the earth.
As far as I know, the energy density of a gravitational field is a lot less obvious than the energy density of a electric and magnetic fields. Gravitational radiation is much less a part of our daily lives than the nearly omnipresent electromagnetic radiation, and so experimental evidence that gravitational field has mass when it is in gravitational radiation may not be available.
The energy stored in a spring is associated with higher electric fields inside the lattice of the spring. Those electric fields have a known energy density which by $E=mc^2$ has a known mass density. The mass of electric and magnetic fields is known to be consistent with gravitational "acceleration" of radio waves known as blue shift.
The energy stored in height above a planetary mass it would seem should, by analogy, be stored in the gravitational field. But since Gravity is weak compared to electromagnetic forces, and gravitational radiation is not something we can do much with experimentally, the actual experimental evidence that gravitational potential energy is stored in the gravitational field between and around the objects is harder to come by.