A 2008 review of gravitomagnetism is available in this PDF but basically you are asking a question about history and that is harder to answer.
So it wasn’t until the 1830s that we had a preliminary unification just beginning to unfold, between electricity and magnetism. It took another generation to get James Clerk Maxwell’s 1860s observations that the laws as he had them were only consistent if charge did not accumulate at any point, but that if he viewed all of space as made out of little electromagnetic vortices then another term would enter the equations—what we now call a “displacement current”—and as a result these vortices could carry waves which would travel at the speed of light. Even then it took another generation, the 1890s, before we had the Lorentz invention of “local time” and the ether-based tensions brewing between Newton’s theory and Maxwell’s theory. Some have mused that the chief virtue of scientific revolution is that the old generation of scientists die out, allowing new generations to have radical new ideas: the timeline of electromagnetism certainly lends some support to this idea.
It is hard to believe that nobody had the idea of gravitomagnetism before Einstein. For example JJ Thompson’s Recent Researches in Electricity and Magnetism starts out with a discussion about how “Faraday tubes” (we’d call them electric field lines now) are instrumental to understanding electricity and magnetism, and that magnetism in fact gives us a fundamental idea that there might be a Faraday tube which does not begin and end on a charge but rather loops around on itself, having neither beginning nor end. It then immediately observes that there is a connection between the Faraday tubes and Le Sage’s theory of gravitation (which is that maybe space is filled with particles flying in all different directions and maybe matter absorbs a little bit of them, so that any given mass casts a shadow of these particles in all directions, leading to an attractive $1/r^2$ force between two masses as they sit in each others’ shadow). It is perhaps not a tremendous leap to imagine that perhaps there are analogously gravitational Faraday tubes and perhaps some of them do not terminate on masses but rather just loop around. But if Thomson made this leap then I do not know about it; he probably would have immediately objected that the force directions are opposite (like attracts like for gravitation, repels like for electromagnetism) preventing the mechanical analogy that Faraday was chasing.
So the first inklings I can find of gravitomagnetism are maybe in Einstein’s 1912 (four years before general relativity!) paper “On the theory of the static gravitational field, and note added in proof”, which was itself a correction-type paper to a different paper (just flip back several pages) also being published in 1912, itself a response to a third paper in 1912 by Max Abraham, with some history in a paper on arXiv. But even here I am not seeing a prediction of classical gravitational waves! Einstein just thinks that light might move slower in a gravitational field, because he is chasing this idea that gravitation should be the same as being in a uniformly accelerated field.
I am surprised that he did not go further immediately; you should surely want a Lorentz-covariant theory of gravitation plus the observation that the Coulomb law looked like the Newton law in having a $1/r^2$ force law corresponding to a straightforward $\operatorname {div} E \propto \rho$ equation. If you want to make this relativistic then you have to consider that moving masses should generate a “magnetic field” and that together these two should have an underlying wave theory.
Right after the above paper you of course have general relativity and then more explicitly the Lense-Thirring papers (paywall warning) which apparently treated gravitomagnetism even more seriously. The reason that gravitomagnetism is not a final theory and you need to “graduate” to general relativity eventually, has to do with the fact that your source (which in electromagnetism is the 4-vector $(\rho, \mathbf J/c)$) is no longer Lorentz-covariant when you write out these equations.
But yeah, the basic reason why classical Newtonian gravity does not predict waves is because before Einstein I can’t find any work into predicting that there would be a magnetic analogue to the “purely electrical” theory of Newtonian gravitation. If you formulate such a theory and then hook up the electric and magnetic fields the way Maxwell did, to get gravitational fields propagating at speed $c$ and gravitational waves when those gravitational fields oscillate suitably: then you have your prediction. But as far as I can tell, nobody had the electromagnetic model to perform this intriguing unification until Maxwell derived that light was just electromagnetic waves: and it looks like before the development of even special relativity folks were just more likely to say “Newton is right, Maxwell is wrong” than to say “Hm, maybe we can steal these ideas from Maxwell to say something interesting about Newton, too.” But with special relativity, Einstein’s hand was kind of forced, he was committing very strongly to “Maxwell is righter than he could ever have known” and this meant that Newton’s idea of instantaneous gravitational-force at a distance could no longer be sustained, since once you have special relativity, instantaneous forces (if you can choose multiple different reference frames for different forces to be instantaneous in) can transmit information backwards in time.
