Notice that $\{k^{2n}/p\} = r_k/p$, where $r_k$ is the remainder $k^{2n}$ leaves upon division by $p$. Clearly, the $r_k$ are quadratic residues modulo $p$.
If $p$ is prime, and $p-1$ and $n$ are relatively prime, then the $r_k$, $k = 1, \dots, (p-1)/2$, are pairwise distinct, since the $k^{2n}$, $k = 1, \dots, (p-1)/2$, are pairwise distinct modulo $p$, by Fermat's little theorem. In this case, the $r_k$, $k = 1, \dots, (p-1)/2$, form the set $R$ of all $(p-1)/2$ quadratic residues modulo $p$ in the range $1$ through $p-1$.
If, in addition, $p$ is congruent to $1 \pmod 4$, then $-1$ is a quadratic residue modulo $p$, and the assignment $r \mapsto p-r$, $r \in R$, defines a permutation of $R$. In this case, $\sum_{r \in R} r = \sum_{r \in R} (p-r) = p(p-1)/2 - \sum_{r \in R} r$, so $\sum_{r \in R} r = p(p-1)/4$, and the arithmetic mean in question is $1/2$.
Finally, since $n$ is odd, infinitely many primes congruent to $1 \pmod 4$ are also congruent to $2 \pmod n$, by Dirichlet's theorem on arithmetic sequences of integers; for such a prime $p$, the numbers $p-1$ and $n$ are clearly relatively prime. This completes the proof.

It is sufficient to show that $\sum_{k=1}^{(p-1)/2} \{k^{2n}/p\} = (p-1)/4$ for every prime $p$ congruent to $1 \pmod 4$.
Let $p$ be a prime congruent to $1 \pmod 4$, let $K = \{1, \dots, (p-1)/2\}$, let $r_k$, $k \in K$, be the remainder $k^2$ leaves upon division by $p$, and let
$$K^{-} = \{k : r_{k} < p/2\} \quad \text{and} \quad K^{+} = \{k : r_{k} > p/2\}.$$
It is easily seen that the $r_k$ are pairwise distinct, so they form the set of all quadratic residues modulo $p$. Since $p$ is congruent to $1 \pmod p$, $-1$ is a quadratic residue modulo $p$, so there is a bijection $f: K^{-} \to K^{+}$ such that $r_k + r_{f(k)} = p$ for all $k$ in $K^{-}$; in particular, $|K^{-}| = |K^{+}| = |K|/2 = (p-1)/4$.
Since $n$ is odd, it follows that $k^{2n} + f(k)^{2n} \equiv 0 \pmod p$ for all $k$ in $K^{-}$, so if $r'_k$ is the remainder $k^{2n}$ leaves upon division by $p$, then $p - r'_k$ is the remainder $f(k)^{2n}$ leaves upon division by $p$. Consequently,
$$\begin{aligned} \sum_{k \in K} \{k^{2n}/p\} &= \sum_{k \in K^{-}} \{k^{2n}/p\} + \sum_{k \in K^{+}} \{k^{2n}/p\} = \sum_{k \in K^{-}} (\{k^{2n}/p\} + \{f(k)^{2n}/p\}) \\ &= \sum_{k \in K^{-}} (r'_{k}/p + (1 - r'_{k}/p)) = |K^{-}| = (p-1)/4. \end{aligned}$$