While $M=n^{O_p(1)}$ can be tricky (or out of reach), improving the trivial bound $M\le p^{\varphi((p-1)n)}$ one can showfollowing argument shows that, indeed $M\le p^{(2+o(1))\sqrt{dn}}$ with $d=\gcd(p-1,n)$; thus, $M\le p^{(2+o(1))\sqrt{(p-1)n}}$ holds$M<\exp(O(\sqrt n))$ in the regime where $p$ is fixed and $n$ grows. To this end, recall
Recall that the critical number of a finite abelian group $G$ is defined to be the smallest positive integer $k$$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 elements of pairwise distinct elements of $A$. It is known that theif $G$ is cyclic, then its critical number of any finite abelian group is at most $(2+o(1))\sqrt{|G|}$ (just google; see, for instance the references)paper by Hamidoune, Llado, and Serra "On Complete Subsets of the Cyclic Group".
Let now $k$ being the critical number of the group ${\mathbb Z}/((p-1)n){\mathbb Z}$${\mathbb Z}/dn{\mathbb Z}$, so that $k\le(2+o(1))\sqrt{(p-1)n}$$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{(p-1)n}$$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}\}\subset {\mathbb Z}/((p-1)n){\mathbb Z}$$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 equal todivisible by $0$$dn$, and we define $M$ to be the claim followssum 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.