An interesting question to which I do not know the answer! My recollection is that I first thought about energy when learning about Joule and work-heat equivalence. But maybe I'd met KE before and not thought much about it.
If you do have a concept of KE, then PE seems obvious. When an object falls, it gains speed and hence KE due to the acceleration caused by gravity. So when an object is high up, it has the potential to gain KE by falling. Or if an object has speed, KE, then it has the potential to rise up against gravity.
Quantitatively the change in KE with height when moving in a gravitational field works out at mgh, so that becomes the PE.