Is it true that the predictions from the General Theory of Relativity don’t match the observations of galaxy rotation speeds, and that this then started the search for dark matter? Is it only the rotation speeds of galaxies that are in conflict with GR or are there other observations that that don’t match the predictions as well?
General Relativity has nothing to do with the galaxy orbital speed. General relativity describes strong gravitational fields and the global geometry of spacetime. However, in the limit of the weak field, General Relativity simply matches the Newtonian gravity since the Newtonian gravity already matches the observation for the weak field.
Because gravity on the galactic scale is extremely weak, the orbital speed contradiction is with the Newtonian gravity. There is no direct contradiction with General Relativity, but only through the Newtonian gravity. It is not conceptually impossible that one day someone finds some additional initial or border conditions or some other conditions that would make General Relativity at the galactic scale different from the Newtonian gravity thus resolving the contradiction.
Currently there are two main approaches to resolve this issue. One is to assume the existence of the Dark Matter. The pros are that this assumption explains the observations, including Gravitational Lensing. The cons are that the dark matter itself has not been observed and currently is not a part of the Standard Model of elementary particles. Another approach is modifying the Newtonian gravity on the galactic scale. One such an attempt is known as MOND or Modified Newtonian Dynamics. The pros are that the unobserved dark matter is not required. The cons are that the observational evidence is not fully explained and no obvious fundamental theoretical basis for the modification.