Why are coordinates and velocities sufficient to completely determine the state and determine the subsequent motion of a mechanical system?

You should think of this by timestepping Newton's laws--- if you know the positions and velocity and one instant, you know the force, and the force determines the acceleration. This allows you to determine the velocity and an infinitesimal time in the future by

$$ v(t+dt) = v(t) + dt F/m $$ $$ x(t+dt) = x(t) + dt v $$

You then find the position and velocity at the next time step, and you find the new force, and continue forever. This is an algorithm to solve Newton's laws, and all that LL are saying is that Newton's laws are known from experience with objects, they are inducted from observations.

"known from experience" in here means "known from experience that first order derivatives in the Lagrangian or second order in the equations of motion are enough". I think their basis for this assertion is very Occamian (but who could know with certainty what L&L were thinking about?) The non-Occamian approach to this answer is given in the post you quoted in your question.

For the last question indeed you can determine $\dot{q},\ddot{q},\ldots,$ from $q$ alone if you already know $q$. But wait! wasn't finding $q$ the problem? and, how are you suppose to determine $q$? Solving a second order equation, for which you need initial conditions ($q_0,\dot{q}_0$).