Axioms, by definition, are not required to have a justification. The need to agree with the evidence, but that's it. For instance, the axioms of quantum theory.
My understanding is that the principle of least action and Newton's laws can each be used to prove the other. So which is the axiom and which is the theorem is a matter of choice and perspective. That Newton's laws appear more axiomatic to us than the principle of least action may have only to do with the kind of intuitions that evolution has hard-wired into our brains. Pushes, pulls, and accelerations are magnitudes that animals need to immediately process in order to survive.