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.