$k = 2, 3, 5, 6$ can be handled easily since if $d \mid 30$, $\sum_{x \in \mathbb{Z}_{31}} f(x)^{30 / d} \equiv \sum_{x \in \mathbb{Z}_{31}} x^{30 / d} \pmod {31}$ and from some calculation, we can prove that this can never hold. Now, if $k = 4$, notice that this is ELMO 2024 P6, which finishes the problem as $x \mapsto x^7$ satisfies the statement.

This problem asks to find the least degree permutation polynomial over the field $\mathbb{F}_{31}$ whose degree is no less than $2$. This can be MANUALLY solved through the theorem about permutation polynomials. First of all, the polynomial $p(x) = x^7$ is a permutation. Now note the following theorem of Hermite; TFAE a. there exists a $30$ degree polynomial $g(x)$ such that $f(x)^{30} \equiv g(x) \pmod{x^{31} -x}$ and for each $t = 1,2, \ldots 29$, $f(x)^t$ is equivalent to a polynomial with degree no larger than $29$ modulo $x^{31}-x$. b. $f$ is a permutation. Now we will show that there is no permutation polynomial of degree $2$, $3$, $4$, $5$, $6$. In general, being permutation is invariant under translations $f(x) \longrightarrow f(x-a)$ and $f(x) \longrightarrow f(x) +b$, it suffices to consider the polynomials of type $f(x) = x^n + ax^{n-2} + \cdots + x$. If $n=2$, $f$ is not permutation since it is $2:1$ on the reduced residue system. The polynomial $f(x) = x^3 +ax$ can be removed from $f(x)^{10} \equiv x^{30} + \cdots \pmod{x^{31}-x}$. Polynomial $f(x) = x^4 + ax^2 + bx$ is removed since $f(x)^8 \equiv 8ax^{30} + 8bx^{29}+ \cdots $ so $a=b=0$. Polynomial $f(x) = x^5 + ax^3+bx^2+cx$ is excluded from $f(x)^6 \equiv x^{30} + \cdots $. Polynomial $f(x) = x^6 + ax^4 + bx^3 + cx^2 +dx$, then $f(x)^5 \equiv x^{30} + \cdots$ so impossible. Therefore the answer is $7$.