$V$ fixed/background
Let's begin by not worrying about what's sourcing the potential. If the physics is well-described in a particular frame by a potential $V$, we may (following the OP) set that potential to be the time component of a 4-vector potential $A$, which will then give a Lorentz-invariant theory. I'm not sure how to interpret the space-like components of $A$, but it is worth pointing out that in the case of Newtonian gravity, $V=-GMm/r$, one obtains the theory of gravitoelectromagnetism. In other words, perhaps the best we can do to interpret the components is to make an analogy with electromagnetism (we'll see velocity-dependent deflection after making a boost).
Of course this procedure is not a unique way to build a Lorentz invariant theory from a Newtonian one. Let us work using $4$-forces rather than $4$-potentials. Then we can write a $4$-version of Newton's Second Law:
$$F^\mu(x,v)=m_0\frac{dv^\mu}{d\tau},$$
where $x$ is the position and $v$ is the $4$-velocity. Expanding about $v=0$ gives:
$$m_0 \frac{dv_\mu}{d\tau}=F^{(0)}_\mu(x)+F^{(1)}_{\mu\nu}(x)v^\nu+F^{(2)}_{\mu\nu\sigma}(x)v^\nu v^\sigma+\cdots\tag{1}$$
The condition that the $4$-force be orthogonal to the $4$-velocity sets $F^{(0)}_\mu$ equal to $0$, $F^{(1)}$ to something antisymmetric, etc. It's clear that we need to keep at least $F^{(1)}$, which gives E&M-type theories. But Lorentz-invariant extensions that put the nonrelativistic 3-force $F_i$ into $F^{(2)}_{itt}$ rather than into $F^{(1)}_{it}$ are, I think, also possible.
$V$ sourced by matter
If we care about the way $V$ is sourced, we enter the domain of field theory, which is more constrained than the previous case. Before, we could allow the $F^{(i)}$ to vary arbitrarily over spacetime because an arbitrary preset background was okay (since the nonrelativistic potential was taken as an arbitrary preset background). But we are supposed to build the Lagrangian density of a Lorentz-invariant field theory only from the fields and their derivatives. Under strong assumptions like locality/renormalizability/etc, I believe we obtain the theories in Bruce Greetham's answer, but let's try a slightly more general context.
Assume a vector current $j^\mu$ sources the potential (like E&M but unlike GR), and assume the theory is linear (so only the matter, and not the potential field itself, sources the potential). Then we have a field equation that looks like:
$$F^\mu[A]=j^\mu,$$
where $F$ is some linear operator. Taking the Fourier transform, inverting $F$, and using that we only have $A$ and $k$ available to us to build Lorentz-invariant quantities, gives (I think):
$$A^\mu=(R(k)\delta^\mu{}_\nu+S(k)k^\mu k_\nu)j^\nu,$$
where $R$ and $S$ are arbitrary functions of $k$. Plugging in $j^\nu=\delta^{(3)}(x)\delta^\nu{}_0$ and looking at the $A^0$ term may give constraints about the $V$'s that may arise from such a theory, but I couldn't quite figure this out. (For instance, we obviously need 3-rotation-invariance, but I'm not sure if any 3-rotation-invariant $V$ arises for the right choice of $R$ and $S$. Contrast this with the previous section, where even non-rotationally-symmetric $V$'s could be promoted to $A$'s).
