Calculating gravity when taking into account the change of gravitational force

I think that your paradox results from the first equation assuming constant acceleration, which won't be the case if you calculate gravity using the inverse-square law of Universal Gravitation as opposed to just assuming a constant g.

As for what formula you could use to calculate the position of your object when taking into account Universal Gravitation...let's just say the calculations I tried out weren't too pretty.

Here's the problem: since you can't use the formulas for kinematics that assume constant acceleration anymore, you have to go back to Newton's Second Law and plug in the law of Universal Gravitation directly (NOTE: in the equations below I call the distance between the two bodies r instead of y, and I write that your "little" mass has mass M...no worries though, as it will indeed get cancelled out!): $$ -GmM/r^2 = Ma_r $$

This gives you the following second-order nonlinear ordinary differential equation:

$$ \ddot{r} + Gm/r^2 = 0 $$ Wolfram Alpha found an analytical solution to this, but it is cumbersome to the point of uselessness. So I guess that's the formula you are looking for (minus needing to include the necessary constants)...like I said, though, it isn't too pretty!

You are correct that the "normal" formula $y = h - gt^2/2$ doesn't work when the gravitational acceleration changes, so you need a different formula. The mathematical expressions are a little ugly, though. Steven laid the groundwork for this, but I'm going to point you to an earlier answer of mine where I did the calculation. The result comes out to be

$$t_f - t_i = \frac{1}{\sqrt{2G(m_1 + m_2)}}\biggl(\sqrt{r_i r_f(r_i - r_f)} + r_i^{3/2}\cos^{-1}\sqrt{\frac{r_f}{r_i}}\biggr)$$

$r_i$ and $t_i$ are the initial position (height) and time, respectively, and $r_f$ and $t_f$ are the corresponding final values. This equation is a little "backwards" in the sense that instead of expressing position as a function of time, it expresses time as a function of position. You can invert it to express position as a function of time, but you won't find a single nice function for it. You would have to do the inversion numerically, by plugging it into a computer, or by computing a power series or something like that.