Let $n$ be the maximum order. To prove that $x^n\equiv 1\pmod{p}$, it is enough to show that the order of $x$ divides $n$.
Let $a$ be an element of maximum order, and suppose that the order $m$ of $x$ does not divide $n$. Then the lcm $\ell$ of $m$ and $n$ is greater than $n$. We show that there is an element of order $\ell$, contradicting the maximality of $n$.
By considering the prime power factorization of $m$ and $n$, we can find $m'$, $n'$ such that $m'$ divides $m$, and $n'$ divides $n$, and $\gcd(m',n')=1$, and $m'n'=\ell$.
Using $x$, we can construct an element of order $m'$, and using $a$ we can construct an element of order $n'$. But since $\gcd(m',n')=1$, we can construct an element of order $m'n'$, and we are finished.
Added: The following standard result was used in the construction:
Lemma: If $a$ has order $h$ modulo $p$, and $b$ has order $k$, where $\gcd(h,k)=1$, then $ab$ has order $hk$.
Proof: Let $r$ be the order of $ab$. Since $(ab)^{hk}\equiv 1\pmod{p}$, it follows that $r$ divides $hk$. We will show that $hk$ divides $r$.
Note that since $b^k\equiv 1$, we have
$$a^{rk}\equiv a^{rk}b^{rk}\equiv 1\pmod{p}.$$
It follows that $h$ divides $rk$. Since $\gcd(h,k)=1$, it follows that $h$ divides $r$. Similarly, $k$ divides $r$. But since $\gcd(h,k)=1$, it follows that $hk$ divides $r$. This completes the proof.
We know that $a^{\phi(m)}\equiv1$ mod $m$ if $(a,m)=1$ and $a^{\phi(n)}\equiv1$ mod $n$ if $(a,n)=1$. Now let $L=\text{lcm}(\phi(m),\phi(n))$. Then $a^L\equiv1$ mod both $m$ and $n$ if $(a,mn)=1$. So if $(m,n)=1$, then $a^L\equiv1$ mod $mn$ for all $(a,mn)=1$. Finally, if $m,n\gt2$, then $2$ divides both $\phi(m)$ and $\phi(n)$, hence $L\le\phi(m)\phi(n)/2=\phi(mn)/2$ (the final equality because $m$ and $n$ are relatively prime). So there is no element of order $\phi(mn)$, which is to say there is no primitive root.
Remark: This is essentially the same proof as in lhf's answer (which I didn't see until I finished posting).
Best Answer
To elaborate on my comment:
Suppose that $p-1\nmid n$. Then let $g$ be a primitive root $\pmod p$. It follows that $g^n\not \equiv 1 \pmod p$. Also, $g$ is clearly invertible $\pmod p$. That implies that the list $\{g\times 1, g\times 2, \cdots, g\times (p-1)\}$ is a full list of the non-zero residues $\pmod p$.
Thus $$S_n\equiv (g\times 1)^n+(g\times 2)^n+\cdots +(g\times (p-1))^n\equiv g^nS_n \pmod p$$
But then, as $g^n\not \equiv 1$ we see that $S_n\equiv 0\pmod p$ as desired.