So, I mean, let's start with, “yes, you’re right.” Potential energy is “stored” in the abstract coördinates of a system. You can sometimes connect that to a particular object in the system, for example the position of a small mass in a large mass’s gravitational well, assuming that the large mass is immobile. Then it’s just stored in the small mass’s radial position and you can pretend that the energy is stored in there. Or, if you have two masses attached by a spring, the coördinate is the distance between them and, handily enough, you have a spring stretched for that length so it is handy to say that energy is “stored in the spring,” even though if we’re super-pedantic we might say it’s stored in “the strain coördinate of the spring” or so.
Then you run into more strange phenomena. The field components of the electromagnetic field are components that “store energy.” It also stores momentum and angular momentum! If you want those to be stored in concrete objects you have to go all the way to an advanced but of physics called “quantum field theory” to argue that these are stored “in the photons” or so.
What's really happening is that energy is a different way to look at a system, compared with forces. It is just a different mental accounting. And just like real accounting, where a ton of details have to do with “ledger entries” (value transfers) but you can often get a good understanding from summing them up into overall “account balances”, in the energy perspective we sum up a lot of momentum flows and directions to only focus on the speeds of our particles. We lose some information, but we gain an easier way to reason about the system. And in fact if we are lucky, we can sometimes recover the exact dynamics (the transfers underneath, the forces) from a picture of the energy possibilities, often in the form “If I started here and I ended there, what was the set of transfers that had to happen to get me there?” For this in the energy picture we usually need to ignore energy dissipation (friction etc) so that we can say “you had to get this energy from somewhere and it came from here, and such-and-so was the force that needed to happen to perform that work on you.”
The energies that can be unambiguously associated with the particles are kinetic energies, but it is also a mistake to think of those as a stuff because they are not reference-frame invariant. You see a grapefruit standing still on a table and say there is no kinetic energy, I am juggling on a train and I pass by your house and I think that’s a 70 km/hr grapefruit, I am very glad I do not have to catch that right now! The proof is if you tried to gently toss it to me, and I tried to add it to the balls I am juggling: I would lose a hand! Or at least cause a citrus explosion.
Potential energy is just what forces look like in this energy language. Not all forces can easily be brought into this language, but the ones that can are described by a potential energy function that says “given where everything is, here is a number representing the potential energy, and if that number decreases then by the work-energy theorem the kinetic energies have commensurately increased because I have precomputed that such-and-so work was performed on that system by these forces.” So, if forces can be associated with the interaction between two particles then so can energies, if you can take one of those particles for granted (like the Earth) then you can associate the force/energy purely with the other particle.
That we can almost always precompute this value is the surprising thing, that is a manifestation of the “unreasonable effectiveness of mathematics” in describing the world.
- This is kind of like a bus map if you aren’t sick of analogies. :) “You were going North from 3rd and Hamilton on route 7, now you are going East at 12th and Main on route 11, the only way you could have done that without looping all the way around on one of these routes is if you got off at 15th street and took the route 3 bus to State St, then got off there... yeah, from there you could get on Route 7.” For us it is more abstract, the energies are assembled into a “Lagrangian” and a branch of mathematics called “calculus of variations” handles the “if you start here and end there how did you travel between them?” questions.