Yes, it's very similar to the problem of designing a macroscopic robot that can out-compete natural predators of the same size. Early attempts will probably fail completely, and then we'll have a few generations of devices that are only superior in some narrow specialty or in controlled environments.

But just as with robots, the design space of nanotech devices is vastly larger than that of biological life. We can easily imagine an industrial ecology of Von Neumann machines that spreads itself across a planet exterminating all large animal life, using technologies that such organisms can't begin to compete with (mass production, nuclear power, steel armor, guns). Similarly, there's a point of maturity at which nanotech systems built with technologies microorganisms can't emulate (centralized computation, digital communication, high-density macroscopic energy sources) become capable of displacing any population of natural life.

So I'd agree that it isn't going to happen by accident in the early stages of nanotech development. But at some point it becomes feasible for governments to design such a weapon, and after that the effort required goes down steadily over time.