Could they have existed from the very beginning? Could they be leftover fragments of the cosmic egg?
If SMBHs were present from the very beginning, I think we would have evidence of that. There would be nothing to stop them accreting and forming quasar-like objects and so the co-moving density of quasars would be high at very large redshifts. But there is clear evolution in the quasar density, peaking at redshifts 2-3. The number density declines by orders of magnitude at higher redshifts and the rate of decline appears to accelerate beyond redshifts of 6. Nevertheless, the presence of any SMBHs beyond redshifts of 6 is quite challenging for theoretical models (e.g. see Is there a limit as to how fast a black hole can grow? ).
I think it also means then that there would be no "dark ages", since the radiation from the quasars would be capable of re-ionising the universe. Yet there is evidence from the Gunn-Peterson effect (demonstrating that the universe was opaque and then re-ionised) that this happened later at redshifts of about 6. This would mean that SMBHs could not be common any earlier.
In fact, I wonder whether there would also be an observable signature in the CMB, since the presence of quasars at such an early stage may have prevented recombination in large "Stromgren spheres" around them.