As I understand, the main question that you ask is: "Does the fact that we get Newton's second law mean that the Lagrangian formulation (and therefore the principle of least action) is correct?"
To my taste this question can not be asked of the physics as we know it. What the physics must do is to describe experimental phenomena in such terms as to be able to predict new ones. We all know that this can be done by making use of some maths and by assigning some measurable quantities to physical processes, such as velocity of a particle, its mass, charge and so on.
If we say that a movement of a particle is described (and predicted given the initial data) by $F=m\ddot{x}$, this does not mean that the particle actually calculates its own acceleration and moves according to what sir Newton formulated. So the Newton's law is just a way to encode all the experimental data, past and future, in one nice formula. The same about other physical laws.
Now, we have a set of different laws: mechanics, electromagnetism, GR, etc. In a search of some principle that unifies all these laws we discover a prescription, that by doing very similar steps allows to reproduce all of them. Since, these laws themselves are just prescriptions to predict phenomena we are just one step higher. However, we have something more universal, less model specific and more flexible. This is what we call "more fundamental".
So, the answer is: no, it is not a coincidence, this is an intentionally designed prescription that allows to reproduce Newtons law from just one function $\mathcal{L}$. Why we like this prescription among others? Well, because there are basically no others. The principle of least action is the most fundamental (read universal and flexible) prescription to unify physical laws, that we in classical physics. In quantum physics we go further and come to the prescription of path integral.
Hence, what about the physical meaning. Many years ago I used to read books by Arnold about geometry of mechanical systems and it seems that there was some geometric sense of $\mathcal{L}$, but I do not remember exactly. You may try to find yourself. However in general there is nothing particular in the form $\mathcal{L}=T-V$ of classical mechanics as in field theory this is already not so straighforward.
My point is, that all physical laws including the least action principle are just prescriptions that allow us to predict phenomena. We can not ask if a prescription is correct or not: as long as it gives good predictions it is "correct" at that stage. In this sense the least action principle is correct as is any other law of physics.