You cite the example of a (Newtonian) gravitational potential which, naively, seems to depend on the position of the bodies under consideration. However, a little more contemplation is warranted here.
Consider the following: When we ask a basic question about the gravitational potential energy of some body relative to Earth, does we have to specify where Earth and this body are located in the Universe? No, we don't. This should arouse the suspicion that something slightly more subtle is going on here.
The reason why we don't have to specify such things is that the gravitational potential only depends on the relative positions of the two gravitationally interacting bodies: $\lvert\vec{r}_1-\vec{r}_2\rvert$. The gravitational potential energy is given by $$U=-G\frac{m_1m_2}{\lvert\vec{r}_1-\vec{r}_2\rvert} $$ The quantity $\lvert\vec{r}_1-\vec{r}_2\rvert$ is (by definition) invariant under any transformation that preserves the distances between points. This includes both rotations and translations. Thus, Noether's theorem applied to the Lagrangian for two gravitationally interacting bodies, given by
$$L=\frac{1}{2}\left(m_1v_1^2+m_2v_2^2\right)+G\frac{m_1m_2}{\lvert\vec{r}_1-\vec{r}_2\rvert} $$
does actually show that momentum (both linear and angular) is conserved.