Why are Maxwell's equations correct and not Newton's laws of motion?

I think there can be several reasons.

First, mankind always wants to complicate his existence on the earth...

Apart from jokes, the simplest reason I could think of is that a finite propagation velocity for light was already proven or, metaphorically speaking, "in the air".

So taking the Maxwell equation, local in their nature and trying to create a model with global view, was the natural consequence of all this: this very first model takes the names of Liénard and Wiechert.

Notice that Lorentz transformations are perfectly hidden inside these equations, that in fact generate changes in electromagnetic field absolutely coherent to those generated by a Lorentz transformation.

To strenghten the validity of the Maxwell equations was the fact that the Galilean transformations could be seen as a limit of those, in situations for which the very high value of $c$ could be approximated to $infty$

To cut a long story short; Einstein pointed it out. Historically, it was well known that Newtonian physics had failed to describe many properties of light (that were explained by Maxwell's equations).

The mistake of most physicists was to try to force matter to behave more like light (using the Lorentz Transform), but using the concept of an "ether" which "caused" the modification as matter "passed through it". Of course the "ether" was entirely undetectable, despite its supposed effect on the properties of matter.

Einstein said "no, we don't need ether, just accept that the speed of light in a vacuum is the fastest anything can go, and you will be fine, same transforms, everything"!

So the Lorentz transform remained correct, but its interpretation was turned on its head.

There is a really nice historical discussion here, which includes a "mathematician's derivation" of the Lorentz transform.

First of all, you can make any transformations you like in both Newtonian physics and Maxwell theory. The key idea is principle of relativity, which states that inertial frames are all equivalent and cannot be distinguished by any experiment.

Back then physicists knew about 2 kinds of interactions - Electromagnetic as described by Maxwell theory and Gravitation as described by Newton theory. Relativity principle when combined with appropriate theory gives you how time and distances need to transform when seen from two different inertial frames. What this means is that you need to make definition of time and space in such a way, to make the transformations work. This was not obvious from the start, but after a time and after a lot of research and it culminated in Einsteins finally realizing this point.

Now gravitational theory was seen as "bad" from the start. Even Newton himself was dissatisfied with the "spooky action at a distance". The force produced by Sun is just instantaneously transmitted on the planets without any mechanism of how is it doing it. On the other hand, Maxwell theory was beautiful, there was some field and the interaction propagated from point to point with some speed, when the change of field only produced change in its immediate neighborhood, just like waves are propagated on a water. No spooky action at a distance. So Maxwell theory was of course preferred over gravitation.

But of course, the Galilean transformations are just common sense. Moreover, the analogy between waves on water and light waves was too good to leave and the field was by many believed to have some material existence. So it was only natural, that physicists first idea back then was that there must be some substance in which these fields live and in which the light propagates. It was not weird, that principle of relativity does not hold anymore for Maxwell theory, as this theory is just attached to this mysterious substance. Just like waves on water do not obey relativity, simply because the water itself is creating preferred frame of reference.

And just like water creates special frame of reference, so does this mysterious substance called eather. The thing to do now, is to find this preferred frame of reference and Michelson-Morley experiment was devised. They did not find any preferred frame of reference. The first idea was that eather is somehow dragged by the movement of Earth. That would explain the negative result, but the explanation was unsatisfactory. What material is dragged by motion of planets, yet does not produce any drag on the planets themselves?

The better idea was searched and was found by Lorentz, Fitzgeral and others. They thought, that because EM field generated by charge is different based on its movement, this change in field itself has consequences on our measuring apparatus - on our clocks and meter sticks. This makes sense, if our metersticks and clocks work on the EM principle. We know they do, as EM is the only interaction except gravitation relevant on human scales. In a way, as EM field is different when meterstick is moving, the forces between molecules are also different and meterstick gets contracted. Lorentz developed this theory and it turned out, that metersticks and clocks get deformed in just the way to make any attempt at finding this preferred frame futile. So the principle of relativity really creeped back in in a very indirect and not very obvious way.

Now comes in Einstein. Einstein was fan of both principle of relativity and Maxwell theory and he had the revolutionary idea that why don't we just define time and space according to what we measure? Ok, it was not as revolutionary, the science was already doing that a lot and positivism was quite influential school of philosophical thought. Especially Ernst Mach, which influenced Einstein quite a lot, is known for his critiques of mechanics in this direction. So the ground was already sat for Einstein to start moving in the right direction. And it is only here, where the abandomnent of galilean transformations arouse by the sheer decision of defining time and space according to our measurement process and not according to our predefined ideas.

But how to make the new definition of time and space to make sense and how to understand it? Einstein simply analyzed what does measuring time and measuring distance really mean. He found out, that there is common denominator which is simultaneity. You simply need to know which events are simultaneous to measure distances and to compare clocks. But how to decide which events are simultaneous? If lorentz theory is to be believed (and gravitation theory not), then the only sensible way to define simultaneity is by using the fact that light is always measured to have the same speed. And from this all follows.

Why is Maxwell's equations correct and not Newton's laws of motion?

At the moment there does not exist a theory of everything in physics. What exist are successful mathematical models of data and observations, which are different for different regions of validity of the variables .

Thus, it is all a matter of region of validity of the variables under consideration. Both are correct, i.e. validated by data observations and predictions, in their region of validity.

Galilean transformations are validated for low velocities and small masses, and the mathematics for the overlap regions of two theoretical models are well defined. For the microcosm there exists quantum mechanics and quantum field theory which can be mathematically shown to be consistent with the classical mechanics and electrodynamics in the overlap region of the value of variables.

The difficulty was only historical, when parallel theories were defined for mechanics and electromagnetism.

How did they understand that the flaw is not in Maxwell's equations but in the Galilean transformations?

where it looked like a disagreement between two successful theoretical models, but it was soon found out, as the other answers state, that no real disagreement existed but the regions of validity of the variables involved had to be carefully examined.