I doubt a replicator came out of thin air. It seems more likely, at least to me, that we started with constructors, that created primitive sequences.

Imagine you have molecules that can form spontaneously, like gliders in Conway's Game of Life. You may have several different molecules that are capable of helping to create one another -- an autocatalytic set.

Eventually this could result in more complex chains, and eventually a self replicating molecule can arise.

Imagine slamming a bunch of gliders together to make a machine that replicates more gliders. It's possible! Not likely, but there are so many variables that can influence the environment substantially. It's not like there was a giant homogeneous soup. Parts from over here and over there would form differently and when they meet, amazing things can happen.

In the Game of Life, this spontaneous event is extremely unlikely, astronomically unlikely.

Unlike Game of Life, the real world has a few advantages that improve performance. For one, it's less fragile. Bonds are much stronger and collisions don't cause everything to break. Another advantage is that bonds are attractive: molecules can rotate and turn to snap together strongly. Gliders just explode violently. And finally, the real world is very dense. We're talking trillions of molecules mixing around millions of times per second per microdroplet. Compound that with a few hundred million years... it certainly doesn't feel as surprising as you might expect.

If there were a highly advanced alien race watching earth over a long period of time, it might be interesting, but not unexpected, that suddenly an Eiffel tower springs forth from the surface of the planet, erected by intelligent organisms.