I assume to work in classical physics. Consider the space $M$ equipped with a Lagrangian local coordinate patch $t, q^1,\ldots, q^n, \dot{q}^1,\ldots, \dot{q}^n$. Assume that the (smooth) Lagrangian of a given physical system takes the form, in that coordinate patch:
$${\cal L}= {\cal L}(t, q^1,\ldots, q^n, \dot{q}^1,\ldots, \dot{q}^n)\:.$$
Then Euler-Lagrange equations read, in that coordinate patch:
$$\frac{d}{dt} \frac{\partial {\cal L}}{\partial \dot{q}^k}= \frac{\partial {\cal L}}{\partial q^k}\:, \qquad \frac{dq^k}{dt}= \dot{q}^k\:, \quad k=1,\ldots, n\:. \quad (1)$$
The second set of equations recalls that $\dot{q}^k$ and $q^k$ have to be considered as independent variables, while their natural relationship holds just on the curves
$$\mathbb R \ni t \mapsto (q^1(t),\ldots, q^n(t), \dot{q}^1(t),\ldots, \dot{q}^n(t))$$
describing the motion of the system.
What happens if changing Larangian coordinates, passing to coordinates $T, Q^1,\ldots, Q^n, \dot{Q}^1,\ldots, \dot{Q}^n$ such that:
$$t=T+c\:,\quad q^k=q^k(T, Q^1,\ldots, Q^n)\:, \quad \dot{q}^k= \frac{\partial q^k}{\partial T}+ \sum_{j=1}^n \frac{\partial q^k}{\partial Q^j}{\dot Q}^j\:,\quad (2)$$
where $c\in \mathbb R$ is a constant, $k=1,2,\ldots ,n$, and the written transformation is supposed to be smooth with inverse (of the same type) smooth?
(The transformation $t=T+c$ simply states that, in classical physics, time is absolute and can be changed only redefining its origin). It is possible to prove the following theorem.
THEOREM. If defining the new Lagrangian function in the coordinate patch equipped with coordinates $T, Q^1,\ldots, Q^n, \dot{Q}^1,\ldots, \dot{Q}^n$:
$${\cal L}'(T,Q^1,\ldots, Q^n, \dot{Q}^1, \ldots, \dot{Q}^n) :=
{\cal L}(t, q^1,\ldots, q^n, \dot{q}^1,\ldots, \dot{q}^n)\:,\qquad (3)$$
where the new coordinates are related with the old ones via (2), then a smooth curve
$$\mathbb R \ni t \mapsto (q^1(t),\ldots, q^n(t), \dot{q}^1(t),\ldots, \dot{q}^n(t))$$
satisfies (1) if and only if the corresponding (via the inverse of (2)) curve
$$\mathbb R \ni T \mapsto (Q^1(T),\ldots, Q^n(T), \dot{Q}^1(T),\ldots, \dot{Q}^n(T))$$
solves
$$\frac{d}{dT} \frac{\partial {\cal L}'}{\partial \dot{Q}^k}= \frac{\partial {\cal L}'}{\partial Q^k}\:, \qquad \frac{dQ^k}{dT}= \dot{Q}^k\:, \quad k=1,\ldots, n\:. $$
In practice the theorem says that, if we assume that $\cal L$ is a scalar (as written in (3)), then the solutions of the dynamical equations do not depend on the used coordinates as requested by physics.
REMARK. This result is by no means obvious. For instance if you pass form the Lagrangian formulation to the Hamiltonian one, there is no analogous result: The solutions of dynamical equations do not depend on the used coordinates provided the Hamiltonian function has not scalar behaviour changing Hamiltonian coordinates $(t,q, p) \to (T,Q,P)$. (The problem arises only when time explicitly appears in the transformation of coordinates.)
The mentioned theorem permits us to choose Lagrangian coordinates and Lagrangian function independently. For example, consider a point of matter constrained to stay on a smooth surface $\Sigma$ at rest with a non-inertial reference frame $I'$, whose motion is given with respect to an inertial reference frame $I$. It is clear that the equations simplify if describing the system using coordinates at rest with $I'$ (coordinates on $\Sigma$), since the equation of the surface containing the point does not depend on time in $I'$. However, in $I'$, inertial forces appear, and these have to be included in the Lagrangian giving rise to a complicated functional form. The stated theorem allows one to make an intermediate choice: writing the Lagrangian ${\cal L}|_I := K|_{I}-V|_{I}$ with respect to $I$, so that no inertial force has to be taken into account in $V|_I$, but using coordinates adapted to $I'$. The discussion obviously applies also to the case of both $I$ and $I'$ inertial.
What you say in your question concerning the Lagrangian:
$${\cal L}=\frac12m\left(\frac{dz}{dt}\right)^2-mgz\to L=\frac12m\left(\frac{dz}{dt}\right)^2-mgz-mga$$
has nothing to do with the fact that the Lagrangian is a scalar or not, because you are considering active coordinate transformations instead of passive ones as due in discussing these issues.
You have two coordinate systems $t,z, \dot{z}$ and $T,Z,\dot{Z}$ with
$$T=t\:, \quad Z=z+h\;, \quad \dot{Z}= \dot{z}\:.\qquad (4)$$
Assuming that the Lagrangian is a scalar means nothing but that, if in coordinates $t,z,\dot{z}$:
$${\cal L}(t,z,\dot{z}) =\frac12m\left(\frac{dz}{dt}\right)^2-mgz\:,\qquad(5)$$
the Lagrangian in coordinates $T,Z,\dot{Z}$ must verify:
$${\cal L}'(T,Z,\dot{Z})=\frac12m\left(\frac{dz}{dt}\right)^2-mgz$$
so that, exploiting (4):
$${\cal L}'(T,Z,\dot{Z})=\frac12m\left(\frac{dZ}{dT}\right)^2-mg(Z-h)$$
that has a different form from (5), but it does not matter!
What is physically (a bit) unexpected from your example is that the form of the Lagrangian changes changing reference frame, even if the two reference frames are completely physically equivalent. This is not a true problem, just in view of the stated theorem and the discussion following the REMARK above: There are many equivalent Lagrangians for the same physical system. If in coordinates $T, Z, \dot{Z}$ you start form a Larangian with the same form of ${\cal L}$, I mean:
$${\cal L}'_1 = \frac12m\left(\frac{dZ}{dT}\right)^2-mgZ$$
you obtain the same equation of motion as those obtained from ${\cal L}'$, even if ${\cal L}'_1 \neq {\cal L}'$.
As a final remark, notice that, even if ${\cal L}'_1 \neq {\cal L}'$, the action functionals associated to these Lagrangians coincide. This suggests another overall viewpoint on these issues, but I do not want to open another long discussion here.
