Yes, $u$ must be a polynomial of degree $2$.
I had to draw on a few unexpected ingredients to prove this;
perhaps there's a simpler proof.
[EDIT Or maybe not: Peter Mueller's answer reports that
this was "an open problem on planar functions for many years",
and gives links to three independent papers c.1990 that independently
solved it. Two of them give the same argument that I found 23 years later,
and the third, by Hiramine, either avoids or re-proves Segre's theorem
but is even more complicated.]
Let $\kappa$ be the finite field ${\bf Z}/p{\bf Z}$
(usually this would be called $k$, but that letter's already taken).
Fix a nontrivial $p$-th root of unity $\rho \in {\bf C}$,
say $\rho = e^{2\pi i/p}$; for any $n \in \kappa$
we shall naturally use $\rho^n$ to mean $\rho^{\tilde n}$
for any lift $\tilde n$ of $n$ to ${\bf Z}$.
Let $K$ be the $p$-th cyclotomic field ${\bf Q}[\rho]$,
and $A = {\bf Z}[\rho]$ its ring of algebraic integers,
which contains the Gauss sum
$\gamma := \sum_{n \in \kappa} \rho^{n^2} \in A$,
with $\gamma^2 = \pm p$ according as $p \equiv \pm 1 \bmod 4$.
For any $p$-th roots of unity $\omega,\zeta \in A$ with $\zeta \neq 1$,
define
$$
G(\omega,\zeta) = \sum_{k \in \kappa} \omega^k \zeta^{u(k)}.
$$
I claim that $G(\omega,\zeta)$ is $\pm\gamma$ times some $p$-th root of unity
(as it must be if $u$ is quadratic).
We prove this by mimicking the usual proof of $\left|\gamma\right|^2 = p$: write
$$
\left|G(\omega,\zeta)\right|^2
= \mathop{\sum\sum}_{k,k' \in \kappa}
\omega^{k'-k} \zeta^{u(k')-u(k)}
= \sum_{l \in \kappa} \left[
\omega^l \sum_{k \in \kappa} \zeta^{u(k+l)-u(k)}
\right]
$$
where $l=k'-k$; now for $l=0$ the inner sum is $\sum_k 1 = p$,
and for $l\neq 0$ the inner sum vanishes by the hypothesis on $u$
(it is a permutation of $\sum_{n\in\kappa} \zeta^n = 0$), so
$\left|G(\omega,\zeta)\right|^2 = p$. This holds for every
Galois conjugate of $G(\omega,\zeta)$, so the algebraic norm of
$G(\omega,\zeta) \in K$ is $p^{(p-1)/2}$.
Because there's a unique prime of $K$ above $p$, it follows that
$\gamma^{-1} G(\omega,\zeta)$ is an algebraic integer
all of whose Galois conjugates have absolute value $1$.
By a theorem of Kronecker this integer must be a root of unity.
This proves the claim that $G(\omega,\zeta)$ is of the form
$\pm\zeta^s\gamma$, because the only roots of unity in $A$
are powers of $\rho$ and their negatives.
[EDIT Gluck's paper (Discrete Math. 80 (1990) 97$-$100)
cites Theorem 1 of "Cavior, S.: Exponential sums related to polynomials
over GF(p), Proc. A.M.S. 15 (1964) 175$-$178" for the result that
$\pm\zeta^s\gamma$ are the only elements of absolute value $\sqrt p$ in $A$.]
Now for any $c \in \kappa$ we have
$G(\rho^c,\rho) = \sum_{k \in \kappa} \rho^{u(k)+ck}$,
which is a representation of some $\pm\rho^a\gamma$ as
a sum of $p$ powers of $\rho$.
This representation is unique because the cyclotomic polynomial
$\sum_{n=0}^{p-1} X^n$
is irreducible and does not vanish at $X=1$.
We already know one such representation,
$\pm\rho^s\gamma = \sum_{n\in\kappa} \rho^{an^2+s}$,
where $a$ is a quadratic residue or nonresidue of $p$
according to the choice of plus or minus sign.
Therefore $u(k)+ck$ must take the same values and multiplicities as
$an^2+s$ when $k$ varies over $\kappa$.
In particular each $b \in {\bf Z}/p{\bf Z}$ occurs at most twice as $u(k)+ck$.
(Could this conclusion have been reached without the foray into
algebraic number theory?)
This strongly suggests that $u$ must be quadratic,
but the implication is still not obvious.
To reach that conclusion we use a
theorem
of Segre
on ovals in algebraic projective planes of odd order.
Recall that an oval in a projective plane $\Pi$ of order $q$
is a $(q+1)$-element set of points of $\Pi$ that meets each line
in at most $2$ points. For example, a conic in an algebraic
projective plane is an oval.
Theorem (Segre 1955). If $F$ is a finite field of odd order
then every oval in ${\bf P}^2(F)$ is a conic.
Now we have just proved that the subset
$\lbrace (x,y) = (k,u(k)) : k \in \kappa \rbrace$
of the affine plane $\kappa^2$ meets every line $cx+y=b$ in at most two points;
it also meets every line $x=x_0$ in exactly one point. Thus we can construct
an oval ${\cal O}$ in ${\bf P}^2(\kappa)$ consisting of these points
$(k:u(k):1)$ together with the point at infinity $(0:1:0)$.
By Segre's theorem $\cal O$ is a conic.
Since it meets the line at infinity at just the one point $(0:1:0)$,
this conic ${\cal O}$ consists of that point together with the graph of
a quadratic polynomial, QED.
