@Matt F. : thanks for the indepndent confirmation.

@Iosif Pinelis: I've added more details, please let me know if anything's still unclear.

I'm not so sure that it's well known (do you a have source where it is explicitly stated?). If you're content with a MO-reference you can cite the last solution here:mathoverflow.net/questions/147270/expected-supremum-of-‌​average

@Anush: Sorry, I have no idea what the lower bound should be for $k=3$ or any other odd $k$. (I have only found a construction which gives slightly lower (asymptotically equivalent) bounds than in the $k=4$ case.)

In the sum in my previous comment the upper index should be $k-1$ (sorry for the typo!).

For $k$ fixed and $d \longrightarrow \infty$ the bounds converge to $\sum_{i=0}^k \frac{(-1)^i}{i!}$

20 years ago (standardization of AES) the differential optimality of $x\mapsto x^{254}$ (your $p(x)$) on $\mathbb{F}_{2^8}$ was a still a conjecture. Is it now kown that differentially 2-uniform permutations of $\mathbb{F}_{2^8}$ do not exist?

Such "extreme low degree" polynomial respresentations are impossible. This can be shown by noting that the Boolean degree of the (the Boolean function) most signifcant bit of addition $\bmod\,2^n$ is $n$, and that the boolean degree of any Boolean coordinate function of $\mathbf{x}^j\mathbf{y}^k$ is at most $|j|+|k|$, where $|\cdot|$ denotes Hamming weight (the number of 1's in the binary representation).

@DieterKadelka: Thanks, corrected!