There are already several good answers. However, the off-shell aspect related to Noether Theorem has not been addressed so far. (The words on-shell and off-shell refer to whether the equations of motion (e.o.m.) are satisfied or not.) Let us rephrase the problem as follows.
Consider a (not necessarily isolated) Hamiltonian system with $N$ degrees of freedom (d.o.f.). The phase space has $2N$ coordinates, which we denote $(z^1, \ldots, z^{2N})$.
(We shall have nothing to say about the corresponding Lagrangian problem.)
Symplectic structure. Usually, we work in Darboux coordinates $(q^1, \ldots, q^N; p_1, \ldots, p_N)$, with the canonical symplectic potential one-form
$$\vartheta=\sum_{i=1}^N p_i dq^i.$$
However, it turns out to be more efficient in later calculations, if we instead from the beginning consider general coordinates $(z^1, \ldots, z^{2N})$ and a general (globally defined) symplectic potential one-form
$$\vartheta=\sum_{I=1}^{2N} \vartheta_I(z;t) dz^I,$$
with non-degenerate (=invertible) symplectic two-form
$$\omega = \frac{1}{2}\sum_{I,J=1}^{2N} \omega_{IJ} \ dz^I \wedge dz^J = d\vartheta,\qquad\omega_{IJ} =\partial_{[I}\vartheta_{J]}=\partial_{I}\vartheta_{J}-\partial_{J}\vartheta_{I}. $$
The corresponding Poisson bracket is
$$\{f,g\} = \sum_{I,J=1}^{2N} (\partial_I f) \omega^{IJ} (\partial_J g), \qquad \sum_{J=1}^{2N} \omega_{IJ}\omega^{JK}= \delta_I^K. $$
Action. The Hamiltonian action $S$ reads
$$ S[z]= \int dt\ L_H(z^1, \ldots, z^{2N};\dot{z}^1, \ldots, \dot{z}^{2N};t),$$
where
$$ L_H(z;\dot{z};t)= \sum_{I=1}^{2N} \vartheta_I(z;t) \dot{z}^I- H(z;t) $$
is the Hamiltonian Lagrangian. By infinitesimal variation
$$\delta S = \int dt\sum_{I=1}^{2N}\delta z^I \left( \sum_{J=1}^{2N}\omega_{IJ} \dot{z}^J-\partial_I H - \partial_0\vartheta_I\right)+ \int dt \frac{d}{dt}\sum_{I=1}^{2N}\vartheta_I \delta z^I, \qquad \partial_0 \equiv\frac{\partial }{\partial t},$$
of the action $S$, we find the Hamilton e.o.m.
$$ \dot{z}^I \approx \sum_{J=1}^{2N}\omega^{IJ}\left(\partial_J H + \partial_0\vartheta_J\right) = \{z^I,H\} + \sum_{J=1}^{2N}\omega^{IJ}\partial_0\vartheta_J. $$
(We will use the $\approx$ sign to stress that an equation is an on-shell equation.)
Constants of motion. The solution
$$z^I = Z^I(a^1, \ldots, a^{2N};t)$$
to the first-order Hamilton e.o.m. depends on $2N$ constants of integration $(a^1, \ldots, a^{2N})$. Assuming appropriate regularity conditions, it is in principle possible to invert locally this relation such that the constants of integration
$$a^I=A^I(z^1, \ldots, z^{2N};t)$$
are expressed in terms of the $(z^1, \ldots, z^{2N})$ variables and time $t$. These functions $A^I$ are $2N$ (locally defined) constants of motion (c.o.m.), i.e., constant in time $\frac{dA^I}{dt}\approx0$. Any function $B(A^1, \ldots, A^{2N})$ of the $A$'s, but without explicit time dependence, will again be a c.o.m. In particular, we may express the initial values $(z^1_0, \ldots, z^{2N}_0)$ at time $t=0$ as functions
$$Z^J_0(z;t)=Z^J(A^1(z;t), \ldots, A^{2N}(z;t); t=0)$$
of the $A$'s, so that $Z^J_0$ become c.o.m.
Now, let
$$b^I=B^I(z^1, \ldots, z^{2N};t)$$
be $2N$ independent (locally defined) c.o.m., which we have argued above must exist. OP's title question in this formulation then becomes if there exist $2N$ off-shell symmetries of the (locally defined) action $S$, such that the corresponding Noether currents are on-shell c.o.m.?
Remark. It should be stressed that an on-shell symmetry is a vacuous notion, because if we vary the action $\delta S$ and apply e.o.m., then $\delta S\approx 0$ vanishes by definition (modulo boundary terms), independent of what the variation $\delta$ consists of. For this reason we often just shorten off-shell symmetry into symmetry. On the other hand, when speaking of c.o.m., we always assume e.o.m.
Change of coordinates. Since the action $S$ is invariant under change of coordinates, we may simply change coordinates $z\to b = B(z;t)$ to the $2N$ c.o.m., and use the $b$'s as coordinates (which we will just call $z$ from now on). Then the e.o.m. in these coordinates are just
$$\frac{dz^I}{dt}\approx0,$$
so we conclude that in these coordinates, we have
$$ \partial_J H + \partial_0 \vartheta_J=0$$
as an off-shell equation. [An aside: This implies that the symplectic matrix $\omega_{IJ}$ does not depend explicitly on time,
$$\partial_0\omega_{IJ} =\partial_0\partial_{[I}\vartheta_{J]}=\partial_{[I} \partial_0\vartheta_{J]}=-\partial_{[I}\partial_{J]} H=0.$$
Hence the Poisson matrix $\{z^I,z^J\}=\omega^{IJ}$ does not depend explicitly on time.
By Darboux Theorem, we may locally find Darboux coordinates $(q^1, \ldots, q^N; p_1, \ldots, p_N)$, which are also c.o.m.]
Variation. We now perform an infinitesimal variation $\delta= \varepsilon\{z^{I_0}, \cdot \}$,
$$\delta z^J = \varepsilon\{z^{I_0}, z^J\}=\varepsilon \omega^{I_0 J},$$
with Hamiltonian generator $z^{I_0}$, where $I_0\in\{1, \ldots, 2N\}$. It is straightforward to check that the infinitesimal variation $\delta= \varepsilon\{z^{I_0}, \cdot \}$ is an off-shell symmetry of the action (modulo boundary terms)
$$\delta S = \varepsilon\int dt \frac{d f^0}{dt}, $$
where
$$f^0 = z^{I_0}+ \sum_{J=1}^{2N}\omega^{I_0J}\vartheta_J.$$ The bare Noether current is
$$j^0 = \sum_{J=1}^{2N}\frac{\partial L_H}{\partial \dot{z}^J} \omega^{I_0 J}=\sum_{J=1}^{2N}\omega^{I_0J}\vartheta_J,$$
so that the full Noether current
$$ J^0=j^0-f^0=-z^{I_0} $$
becomes just (minus) the Hamiltonian generator $z^{I_0}$, which is conserved on-shell $\frac{dJ^0}{dt}\approx 0$ by definition.
So the answer to OP's title question is Yes in the Hamiltonian case.
See also e.g. this, this & this related Phys.SE posts.
I think the source of your confusion is mathematics, not physics. It is important here (and L&L did mention this) that the system of differential equations is autonomous. If this is the case, than along with solution
$q_i=q_i(t,C_1,\dots,C_{2s}),$
it has a solution
$q_i=q_i(t-t_0,C_1,\dots,C_{2s}).$
Because the former is the general solution, the later must reduced to it, that is, it should be
$$q_i(t-t_0,C_1,\dots,C_{2s})=q_i(t,C_1'(C_1,\dots,C_{2s},t_0),\dots,C_{2s}'(C_1,\dots,C_{2s},t_0)).$$
Putting $C_{2s}=0$, yields
$$q_i(t-t_0,C_1,\dots,C_{2s-1})=q_i(t,C_1'(C_1,\dots,C_{2s-1},t_0),\dots,C_{2s}'(C_1,\dots,C_{2s-1},t_0)).$$
For example, in the case of a free 1D motion $x=C_1t+C_2$. Making the shift in time one has: $$x=C_1t+(C_2-C_1t_0)$$ (expression in brackets is $C_2'$). And letting $C_2=0$ we find $$x=C_1(t-t_0).$$
Best Answer
1) A constant of motion $f(z,t)$ is a (globally defined, smooth) function $f:M\times [t_i,t_f] \to \mathbb{R}$ of the dynamical variables $z\in M$ and time $t\in[t_i,t_f]$, such that the map $$[t_i,t_f]~\ni ~t~~\mapsto~~f(\gamma(t),t)~\in~ \mathbb{R}$$ doesn't depend on time for every solution curve $z=\gamma(t)$ to the equations of motion of the system.
An integral of motion/first integral is a constant of motion $f(z)$ that doesn't depend explicitly on time.
2) In the following let us for simplicity restrict to the case where the system is a finite-dimensional autonomous$^1$ Hamiltonian system with Hamiltonian $H:M \to \mathbb{R}$ on a $2N$-dimensional symplectic manifold $(M,\omega)$.
Such system is called (Liouville/completely) integrable if there exist $N$ functionally independent$^2$, Poisson-commuting, globally defined functions $I_1, \ldots, I_N: M\to \mathbb{R}$, so that the Hamiltonian $H$ is a function of $I_1, \ldots, I_N$, only.
Such integrable system is called maximally superintegrable if there additionally exist $N-1$ globally defined integrals of motion $I_{N+1}, \ldots, I_{2N-1}: M\to \mathbb{R}$, so that the combined set $(I_{1}, \ldots, I_{2N-1})$ is functionally independent.
It follows from Caratheodory-Jacobi-Lie theorem that every finite-dimensional autonomous Hamiltonian system on a symplectic manifold $(M,\omega)$ is locally maximally superintegrable in sufficiently small local neighborhoods around any point of $M$ (apart from critical points of the Hamiltonian).
The main point is that (global) integrability is rare, while local integrability is generic.
--
$^1$ An autonomous Hamiltonian system means that neither the Hamiltonian $H$ nor the symplectic two-form $\omega$ depend explicitly on time $t$.
$^2$ Outside differential geometry $N$ functions $I_1, \ldots, I_N$ are called functionally independent if $$\forall F:~~ \left[z\mapsto F(I_1(z), \ldots, I_N(z)) \text{ is the zero-function} \right]~~\Rightarrow~~ F \text{ is the zero-function}.$$ However within differential geometry, which is the conventional framework for dynamical systems, $N$ functions $I_1, \ldots, I_N$ are called functionally independent if $\mathrm{d}I_1\wedge \ldots\wedge \mathrm{d}I_N\neq 0$ is nowhere vanishing. Equivalently, the rectangular matrix $$\left(\frac{\partial I_k}{\partial z^K}\right)_{1\leq k\leq N, 1\leq K\leq 2N}$$ has maximal rank in all points $z$. If only $\mathrm{d}I_1\wedge \ldots\wedge \mathrm{d}I_N\neq 0$ holds a.e., then one should strictly speaking strip the symplectic manifold $M$ of these singular orbits.