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.
Yes, provided one uses the correct notions of symmetry for the action and the lagrangian.
The setup.
We assume throughout that the action can be written as the integral of a local Lagrangian. Namely, let $\mathcal C$ be the configuration space of the system, then for any admissible path $q:[t_a, t_b]\to \mathcal C$, there exists a local function $L$ of paths such that
\begin{align}
S[q] = \int_{t_a}^{t_b} dt \,L_q(t).
\end{align}
Let a smooth, $\epsilon$-deformation $q(t) \to \hat q(t, \epsilon)$ of paths be given. We will use the $\delta$ notation for first order changes in quantities under such a deformation.
Symmetry defined.
We say that this deformation is a symmetry of the action $S$ provided there exists a local function of paths $B_q$ such that
\begin{align}
\delta S[q] = B_q(t_b) - B_q(t_a)
\end{align}
for all admissible paths $q:[t_a, t_b]\to \mathcal C$. In other words, the action only changes to first order by a boundary term. We say that this deformation is a symmetry (or what Qmechanic calls a quasisymmetry in his response) of the Lagrangian $L$ provided there exists a local function $\Lambda_q$ of paths such that
\begin{align}
\delta L_q(t) = \frac{d\Lambda_q}{dt}(t)
\end{align}
for all admissible paths $q:[t_a, t_b]\to \mathcal C$. In other words, the lagrangian only changes to first order up to a total derivative.
Equivalence of notions of symmetry.
Using these definitions, one can show that a given deformation is a symmetry of $S$ if and only if it is a symmetry of $L$.
Notice that for any deformation, and for any admissible path $q:[t_a, t_b]\to \mathcal C$, one has
\begin{align}
\delta S[q] = \int_{t_a}^{t_b} dt\,\delta L_q(t)
\end{align}
Suppose now, that a given deformation is a symmetry of $S$, and let a path $q:[t_a, t_b]\to\mathcal C$ be given. For each $t\in [t_a, t_b]$ we have
\begin{align}
\int_{t_a}^{t} dt'\,\delta L_{q}(t') = B_{q}(t) -B_{q}(t_a),
\end{align}
Since the deformation is a symmetry of $S$. Taking the derivative of both sides with respect to $t$, and using the fundamental theorem of calculus on the left, we obtain
\begin{align}
\delta L_q(t) = \dot B_q(t)
\end{align}
for all $t\in[t_a, t_b]$. Identifying $B$ with $\Lambda$, we find that the deformation is a symmetry of the lagrangian.
I'll leave the converse to you.
Best Answer
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.
(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.
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.
See also e.g. this, this & this related Phys.SE posts.