Based on what I see in available sources it seems that the answer to my question is "no". But I fail to see why. Here is my line of reasoning:
Consider a theory $T$ which has some prime model $\mathcal{M}$. For any two models of $T$ (let's call them $\mathcal{N}_1$ and $\mathcal{N}_2$) there are elementary embeddings from $\mathcal{M}$ to both $\mathcal{N}_1$ and $\mathcal{N}_2$. This means that $\mathcal{N}_1 \equiv \mathcal{M}$ and $\mathcal{N}_2 \equiv \mathcal{M}$ which shows that $\mathcal{N}_1 \equiv \mathcal{N}_2$. So any two models $\mathcal{N}_1$ and $\mathcal{N}_2$ of $T$ are elementarily equivalent, which means that $T$ is complete.
Where am I getting it wrong?
Based on the comments below the question it turns out that the confusion was due to an unusual definition of prime model.
Usually we say a model $M$ is a prime model of a theory $T$ if it embeds elementarily into every other model of $T$. Using this definition we can indeed deduce that $T$ is complete. A proof of that is already given in the question itself.
So what was the confusion? It turns out that certain sources define a prime model as a model that embeds into every other model of our theory $T$. So in these sources this embedding may no longer be elementary. To be able to conclude that the theory is complete we need this embedding to be elementary. To fix this, one might for example add the assumption that $T$ is model complete, i.e. that every embedding of models is automatically an elementary embedding.