This is not the quickest or easiest proof, but I think it shows conceptually what's really going on here. You can also just do a direct calculation, which you may prefer to what follows.
Perhaps the most basic reason the discrete Fourier basis is important is that it is an eigenbasis for the shift operator $S:\mathbb{C}^N \to \mathbb{C}^N$ which maps $\begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_{N-1} \end{bmatrix}$ to $\begin{bmatrix} x_{N-1} \\ x_0 \\ x_1 \\ \vdots \\ x_{N-2} \end{bmatrix}$.
For example, one of the (unnormalized) discrete Fourier basis vectors is $v_1 = \begin{bmatrix} 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1} \end{bmatrix}$, where $\omega = e^{\frac{2 \pi i}{N}}$ is an $N$th root of unity. What happens when you apply $S$ to $v_1$? You get
\begin{align*}
S v_1 &= \begin{bmatrix} \omega^{N-1} \\ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-2} \end{bmatrix} \\
&= \frac{1}{\omega} v_1 \\
&=\bar{\omega} \,v_1.
\end{align*}
This shows that $v_1$ is an eigenvector of $S$, with eigenvalue $\frac{1}{\omega} = \bar{\omega}$. You can show similarly that the other discrete Fourier basis vectors are also eigenvectors of $S$, and you will find that the eigenvalue of the $k$th discrete Fourier basis vector is
\begin{align*}
\lambda_k &= \frac{1}{\omega^k} \\
&= \bar{\omega}^k \\
&= e^{\frac{- 2 \pi i k }{N}}.
\end{align*}
It follows that the discrete Fourier basis vectors are also eigenvectors of $S^m$, and the $k$th eigenvalue is $\lambda_k^m = e^{\frac{- 2 \pi i m k }{N}}$.
Suppose the discrete Fourier transform of $x \in \mathbb{C}^N$ is $c$, so that
\begin{equation}
x = \sum_{k=0}^{N-1} c_k v_k.
\end{equation}
($v_k$ is the $k$th discrete Fourier basis vector.) Then
\begin{align*}
S^m x &= \sum_{k=0}^{N-1} S^m c_k v_k \\
&= \sum_{k=0}^{N-1} c_k S^m v_k \\
&= \sum_{k=0}^{N-1} c_k \lambda_k^m v_k \\
\end{align*}
which shows that the $k$th Fourier coefficient of $Sx$ is
\begin{align*}
\lambda_k^m c_k &=e^{\frac{-2\pi i m k}{N}} c_k.
\end{align*}
This is what we wanted to show.
