Thought experiments with gravitational potential energy I have come up with two thought experiments regarding gravitational potential energy that confuses me somewhat, and that I'm hoping can be cleared up.
Experiment 1
I take an object and raise it some distance above ground level, where I leave it, so it now has some potential energy corresponding to its height. Then I dig a hole in the ground directly below the object. My first question is, if this will increase the potential energy of the object? My guess is yes, because if the object falls, it will have the ability to make a larger impact at the bottom of the hole than it would have had upon impact with the Earth at ground level.
If my guess is right, then I continue by deciding to push the object sideways, with a movement parallel to the ground. At one point in this movement, it will no longer be above the hole, and there will be a sharp decrement in the potential energy of the object. The energy will make a discontinuous jump, which I admittingly find a bit uncomfortable - but my actual second question is, when there was a decrement in the potential energy, where did it go?

Experiment 2
I lift an object a distance $h$ above ground level, increasing its potential energy, but I keep lifting it indefinitely. I imagine that at one point it will be so far removed from the gravitational pull of Earth that its potential energy starts to decrease again. Indeed, according to this wiki page, the acceleration due to gravity is proportional to the inverse squared distance to the center of the Earth, so if $d$ is this distance, then $g = \frac{k}{d^2}$ for some constant $k$. If I let $r$ be the radius of the Earth, the potential energy is given by
\begin{align*}
E &= mgh\\
&= m\frac{k}{d^2}h\\
&= m\frac{k}{(r+h)^2}h.
\end{align*}
As a function of $h$, this function turns out to be increasing for $h<r$ and decreasing for $h>r$, so as I am raising the object past the point $h=r$, it starts losing energy. My questions are, where is this energy going? And where is the energy that I spend raising the object going, when it is past the point $h=r$?
 A: To 1
The issue here is that the object you lift up does not "have" potential energy. The system consisting of Earth-and-object has potential energy. And this potential energy is calculated for the centres-of-mass. Meaning, as long as the centres-of-mass are separated, there is potential energy stored in this system. The formula, where $d$ is the distance between centres-of-mass, is
$$U=-G\frac{mM}d. $$
If you drop the object over the ground, then a portion of this potential energy is released. If you drop it over the hole, then a larger portion is released. But there is always more to release since we are still far from Earth's core.
Here on Earth's surface with not too large height differences compared to Earth's radius, we typically encompass some of the involved parameters from the potential energy formula into a constant called $g=GM/d^2$. Plug this in to get the shorter version of the potential energy formula that we are more used to:
$$U=-mgd$$
$d$ is still the distance to the centre of the Earth (distance between centres-of-mass). The change in potential energy is all we care about, and we typically symbolise the distance difference with height $h$:
$$E=U_2-U_1=mgd_1-mgd_2=mg(d_1-d_2)=mgh$$
To 2

I imagine that at one point it will be so far removed from the gravitational pull of Earth that its potential energy starts to decrease again

This is not true. Sure, the gravitational force may become so weak with longer distance that the object eventually feels no or at least only negligible gravitational attraction. But don't confuse stored potential energy with the current present force. The attraction may appear absent at the moment - but if that attraction still had a hold, then all the stored potential energy would eventually be released.
In other words, energy can surely be stored and be ready to be released, even though there is no tendency for it to be released at the moment. Just like when you elongate a spring but then tie up the ends. Or when you place a book on a high shelf. That stored energy just waits and waits, since the restoring force is not there (or is overcome by other forces at the moment). But if the restoring force returned, then all this stored energy would be released.
There is indeed more potential energy stored with distance forever with no sudden reduction in energy. If an object is allowed to fall freely back to Earth, then with a longer distance it will be able to reach higher speed (more potential energy to convert into kinetic). Regardless of distance.
To the last half of 2
It seems that you are finding the potential energy associated with a particular position of the object. But keep on mind that only the difference in potential energies matter.
The actual value can be zero without issues (its value just depends on our arbitrary choice of reference which for this formula happens to be at infinitely) - if there is another point associated with negative potential energy then there still is a difference. And that difference might be (numerically) huge when far away.
So, I would start from the original formula for potential energy in general gravitational fields mentioned above,
$$U=-G\frac{mM}d, $$
and find the difference between this value for a point close to and a point far from the Earth:
$$U_2-U_1=G\frac{mM}{d_1} -G\frac{mM}{d_2} =GmM\left(\frac 1{d_1}-\frac1{d_2}\right)=GmM\frac{d_2-d_1} {d_2d_1}=GmM\frac{h} {d_2d_1}$$
As you can see, this result of the potential energy difference is close to but not fully equal to the expression you've reached (in your case, your $k=GM$). We see that a larger distance $h$ between them causes a larger amount of stored potential energy. A larger $h$ means a larger $d_2$ and a smaller $d_1$, and indeed when looking at the part after the first equal sign here, both a smaller $d_1$ and a larger $d_2$ causes a larger overall amount of potential energy.
A: Experiment 1
To calculate potentials of systems you must have a reference point compared to which you give a value to your potential. In fact potentials themselves are not well defined in the sense that you can add any arbitrary value to all potentials like $U'(r) = U(r) + const.$ and yet have the same physics laws:

Conservation of Mechanical Energy
$$
 E_1 = K_1 + U_1, \  E_2 = K_2 + U_2 \quad  then \quad  E_1 = E_2
 $$
$$
 E'_1 = K_1 + U'_1, \  E'_2 = K_2 + U'_2 \quad then \quad E'_1 = E'_2
 $$

and the same Forces:
$$
 F(r) = - \frac{dU(r)}{dr}, \ F'(r) = - \frac{dU'(r)}{dr} = F(r)
 $$

so what is important is the difference between two potentials which is exactly what you get while determining the difference between a reference point and a given point's potential(Hint : In questions potentials should be calculated from the same reference in both sides of equations so that they are consistent)

In your experiment potential does not change as long as you don't change your reference point but if you choose a new point potential can take several values.

Experiment 2

Gravitational potential energy of a system of masses $m$ and $M_e$ a distance r apart is given by(reference point at $r \to \infty$):
$$
 U(r) = - \frac{G m M_e}{r} \ if \  r > R_e
 $$
if $r = R_e + h$ while $h \ll R_e$ we can expand potential energy until first order of approximation:
$$
 U(h) = -\frac{G m M_e}{(R_e + h)} \simeq -\frac{G m M_e}{R_e} + \frac{G m M_e}{R_e^2} h
 $$
where the first term is the potential energy of the system when they are $R_e$ apart which I call ground potential and $g = \frac{G M_e}{R_e^2}$ so:
$$
 U(h) = U_{ground} + m g h
 $$
This shows that your approach to substitute $g$ with an expression is incorrect.
A: 
Then I dig a hole in the ground directly below the object. My first question is, if this will increase the potential energy of the object?

No, because you have to decide in advance where you will put the reference level of potential energy (i.e. where it is zero). If you zero the potential to the original ground level, it will stay zero there, once you have dug the hole, and also after you have pushed the object sideways.
If the object falls into the hole (because you let it go after you have held it up all the time while digging), then its potential energy will decrease (or with respect to the above zero assumption: become negative). What increases is kinetic energy (which is proportional to velocity squared) because the object's velocity increases during the fall. The sum of potential and kinetic energy will stay the same, however.

I imagine that at one point it will be so far removed from the gravitational pull of Earth that its potential energy starts to decrease again

The object will always be under the gravitational pull of the earth if earth is all that exists. Therefore, potential energy will increase forever (i.e. never decrease) if you pull it further and further away from the earth. However, the increments themselves will become smaller and smaller, such that potential energy is tending to a finite value, to below which it is limited.

My questions are, where is this energy going?

After the things I have said above, it should be clear that the question is not where the energy is going (it is actually going into potential energy...), but where it comes from. Either you can burn rocket fuel that feeds the continuous increase of potential energy, or you already start the object (bullet) at ground level with a certain, very high velocity (assuming vertical start). The minimum necessary value for the latter is called escape velocity. For earth, the escape velocity from the surface is ~11 km/s, which is pretty enormous.
If the initial velocity is lower than the escape velocity, the bullet will eventually fall back to ground. If initial velocity is equal to escape velocity, the bullet will end up with velocity zero infinitely away from the earth. And if initial velocity is higher than escape velocity, the bullet will have a remaining velocity when it is infinitely away from the earth. In any case, it is the kinetic energy of the bullet that changes to potential energy (and possibly vice-versa). Total energy (sum of potential and kinetic) is conserved.
