Laplace in 1799 introduced velocity dependence in a particular way, modifying the inverse square law so that the force was directed towards the position retarded according to the relative velocity $v$ and the distance was computed accordingly. The consequence of that was that the correction to the Newtonian force was of the order $v/c$, and, according to Laplace's calculations, the planets would fly off of their orbits in a hurry if gravity propagated at the speed of light. It had to be at least $7×10^6$ times faster than light to match observations.
By the turn of 19th century velocity dependent gravity was instead modeled on Maxwell's electromagnetism, see What 19th century developments contributed to the General theory of Relativity? Gerber in 1898 proposed such a theory in a paper deemed unintelligible, and Lorentz proposed a coherent one in 1900 based on Mossotti's 1830 idea that electric attraction and repulsion do not balance each other exactly and the difference is gravity. They were (implicitly) special relativistic since the Maxwell equations are Lorentz invariant, and in them the correction was of the order $v^2/c^2$. So Laplace's fly off problem did not arise, but they still did not predict the correct precession of the perihelion of Mercury, and did not satisfy the more general relativity principle that Einstein favored. It is these theories that were discussed by contemporary authors like Mach and Poincare, and that Einstein was familiar with. Laplace's theory was not discussed at the time due to its absurd consequences.