The paper uses a minimal weight of 30g and surface area of 1cm² for a replicator. On page 13 it says that you need at least 40 of them to travel through intergalactic space, but also states that there is more mass floating around in interstellar space. The probes should create muliple staging areas.

I assume if such a replicating probe would really be possible, it should be straightforward to just send of a million of them and hope for the best.

In my opinion, a huge limiting factor is communication. How do you know if those probes reached their target?

There's also an ethical aspect to it. Should we really fill the universe with self replicating paperclips? Because once you start the process, when and how would you stop it?