The thing about deterministic time evolution is that there's actually only one degree of freedom: once you have chosen your initial conditions, the single parameter $\Delta t$ is enough to uniquely identify any point along the phase space trajectory.
Assuming time is absolute and time-evolution complete, you can get a maximal set of independent constants of motion by assigning to each point in phase space the coordinates of the point on the given trajectory at $t=t_0$.
This, however, is pretty much useless because it doesn't help you in any way to solve your equations of motion.
A far more interesting result is Noether's theorem (and its generalizations to different formulations of analytical mechanics), which links costants of motion to symmetries of the system.
Consider your example, the Kepler problem (angular momentum and Laplace–Runge–Lenz vector are not constants of motion for arbitrary gravitational fields):
You start with 8 coordinates (3 space coordinates, 1 time coordinate and the associated momenta). The symmetries of your system are translational invariance in time and rotational invariance in space and you end up with 4 constants of motion (energy and the components of the angular momentum vector) corresponding to the generators of the Lie-group of transformations. In principle, it should thus be possible to reduce the problem domain to 4 independant coordinates.
In the Hamiltonian formulation of classical mechanics, you can associate a vector field (a generator of a transformation) to any function on phase space, and there are formal criteria as to when the phase space can be reduced in a certain way which preserves its Hamiltonian structure (the constants of motion must correspond to strongly Hamiltonian symmetries - cf. Marsden-Weinstein redution).
Another possibility to reduce the degrees of freedom of a Hamiltonian system is the Hamilton-Jacobi formalism, where the constants of motion correspond to the integration constants of a partial differential equation for the action function. The spatial coordinates can be kept as independant coordinates, whereas the momenta will be dependent variables given by the derivatives of the action function.