Consider the case in which we shoot an electron up in the stratosphere, it travels up to a certain height and then it stops when its $KE = 0$. We say, according to that principle, that the lost energy is stored as $PE$.
This has been experimentally verified - the electron falling back gains the kinetic energy it lost going up. The concept of potential energy, energy that may be potentially retrieved, has been very successful, and the theoretical framework developed as described by ACuriousMind has been validated again and again and again, i.e., it has not been falsified in the Newtonian framework.
Now suppose that when the electron stops it meets a positron, they annihilate into a photon of equal energy, no more nor less.
NO, two photons are produced. Momentum is a conserved quantity (in the well-validated theoretical framework), and in the center of mass system of an electron-positron, momentum would not be conserved with just one photon. Two particles, at least, are needed for conservation of momentum.
Now we are far away from Newtonian physics. We are in the realm of quantum mechanics and special relativity. The special relativity total four-vector describing the electron plus positron before scattering and annihilating, and after, is invariant - it does not change with the interaction. Thus, the potential energies of the electron and the positron will be taken into account by the energies and directions of the two photons. This is because their center of mass is continuous with the center of mass of the original $e+e-$ pair. The two photons have an invariant mass-energy equivalent that will be affected by the gravitational field - changing the direction of their decay to compensate for the energy. The energy balance will be reflected in the frequency ($e=h\nu$) of the photons.
It would appear evident that its $KE$ has been drained out by $g$ and definitely destroyed. Is this correct?, if you think it is not, where has primitive $KE$ gone?
$KE$ is continuously transmuted to potential, to chemical, to rest mass, to... Kinetic energy is not conserved. It is the total four-vector components of the system, $(E,p_x,p_y,p_z)$ that must be conserved, and they are. Lorentz invariance has been validated experimentally - innumerable times.
If this is correct, does the same conclusion apply to a photon leaving a supermassive body?
In black holes, photons are attracted by the gravitational field too, and conservation of four-vectors always holds.
and being redshifted to $0$?
This redshift business is the realm of General Relativity. In GR even though conservation of four-vectors holds locally, talking of redshifted photons takes us out of locality and into the Big Bang model, General Relativity frame, and the expansion of space itself. This is a research area both experimentally and theoretically and one where to balance energies we have "invented" dark energy and dark matter, so as to keep the conservation of local four-momentum vectors, which is another story.
Please note that I am asking this question in Newtonian physics. Is the answer different in Newtonian and in relativity physics?
Of course it is different, as I explained above.