While $M=n^{O_p(1)}$ can be tricky (or out of reach), the following argument shows that $M\le p^{(2+o(1))\sqrt{dn}}$ with $d=\gcd(p-1,n)$; thus, $M<\exp(O(\sqrt n))$ in the regime where $p$ is fixed and $n$ grows. 

Recall that the *critical number* of a finite abelian group $G$ is defined to be the smallest positive integer $k=k(G)$ such that for any $k$-element subset $A\subset G\setminus\{0\}$, every element of $G$ is representable as a non-empty sum of pairwise distinct elements of $A$. It is known that if $G$ is cyclic, then its critical number is at most $(2+o(1))\sqrt{|G|}$; see, for instance the paper by Hamidoune, Llado, and Serra "[On Complete Subsets of the Cyclic Group][1]".

Let now $k$ being the critical number of the group ${\mathbb Z}/dn{\mathbb Z}$, so that $k\le(2+o(1))\sqrt{dn}$. If the order of $p$ in this group does not exceed $k-1$, then we have $p^s\equiv 1\pmod{dn}$ with some $s\le k-1$, implying $n\mid 1+p+\dotsb+p^{s-1}$; thus, we can set $M:=1+p+\dotsb+p^{s-1}$. Otherwise, consider the set $A:=\{1,p,p^2,\ldots,p^{k-1}\}$. By the definition of a critical number, one can select several elements from this set so that their sum is divisible by $dn$, and we define $M$ to be the sum of these numbers.

---

One further observation is that if $p\equiv 1\pmod n$, then in order for a sum of powers of $p$ to be divisible by $n$, one needs to have at least $n$ such powers; hence, $M>p^{n-1}$ in this case. This does not, of course, show that $M<n^{O(1)}$ fails to hold, as the assumption $p\equiv 1\pmod n$ is incompatible with the regime where $p$ is fixed and $n$ grows.

[1]: http://ac.els-cdn.com/S009731650800006X/1-s2.0-S009731650800006X-main.pdf?_tid=b1682b34-eca9-11e4-aff0-00000aacb35f&acdnat=1430117609_c121a6bfeff2b580151273531596e6e4