For $p=2$ there is an obvious solution.
Note that $256=2^{8}$. So if $2$ is a quadratic residue of $p$, there is an $x$ such that $x^2\equiv 2 \pmod{p}$, and therefore $x^{16}\equiv 256\pmod{p}$. For any prime of the form $p=8k\pm 1$, we have that $2$ is a QR of $p$. Thus our congruence has a solution whenever $p$ is of the form $8k\pm 1$.
For $p$ of the form $8k\pm 3$, we use the following standard result.
Lemma: If $a$ is not divisible by $p$, then $a$ is a $k$-th power residue of $p$ if and only if $a^{(p-1)/d}\equiv 1\pmod{p}$, where $d=\gcd(p-1, k)$.
To apply the Lemma, let $k=16$. Then $\gcd(p-1,k)$ is one of $2$ or $4$. If the $\gcd$ is $4$, we are looking at $256^{(p-1)/4}$. This is $4^{p-1}$. But $4^{p-1}\equiv 1\pmod{p}$ by Fermat's Theorem. The case where $\gcd(p-1,16)=2$ is dealt with similarly.
Thus our congruence has a solution for all primes $p$.