Elementary, direct proof of when $5$ is a quadratic residue mod $p$ $\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$
It's easy to use Quadratic Reciprocity to show that $\kron{5}{p} = \kron{p}{5} = 1$ when $p \equiv \pm 1 \pmod 5$, and is $-1$ when $p \equiv \pm 2 \pmod 5$. 
I'm interested in an elementary, direct proof of when this happens without appealing to either quadratic reciprocity directly or to things like Gauss's lemma (which is sort of like quadratic reciprocity in disguise). For example, this answer gives a direct proof of $\kron 2p$.
For $p \pmod 5$, this is not so bad. For instance, if $p \equiv 1 \pmod 5$, then one can use that $\left( \mathbb{Z}/p\mathbb{Z} \right)^\times$ is cyclic of order divisible by $5$ to get an element of order $5$, and then proceed as in this question. 
But what about when $p \not \equiv 1 \pmod 5$? In particular, how might we handle when $p \equiv -1 \pmod 5$?
 A: Here's a start: If $p \equiv 1$ (mod $5$), then $F = \mathbb{Z}/p\mathbb{Z}$ contains an element of multiplicative order $5$, so $x^{5}-1 = (x-1)(x^{4}+x^{3}+x^{2}+x+1)$ splits into linear factors in $F[x].$ If $\omega \neq 1$ is one of its roots, then $(\omega+\omega^{-1})^{2} = 1- \omega - \omega^{-1}$ so that $x^{2} +x-1$ has a root in $F.$ Then $F$ contains $\sqrt{5}$ by solving the quadratic. 
Continuation: Suppose now that $p \equiv -1$ (mod $5$). Then ${\rm GF}(p^{2})$ contains an element $\omega$ of multiplicative order $5$. Note however that $\omega +\omega^{p} \in {\rm GF}(p).$ Also, as $p \equiv -1$ (mod $5$), we have $\omega^{p} = \omega^{-1}.$ Hence $x^{2}+x-1$ has a root in ${\rm GF}(p),$ so that we still have $\sqrt{5} \in {\rm GF}(p).$ 
I think the other direction follows ( at least for odd $p$) by mimicking the proof of the constructibility of the regular pentagon but working over ${\rm GF}(p).$ More precisely, if ${\rm GF}(p)$ contains $\sqrt{5}$ we can show that a primitive $5$-th root of unity $\omega$ satisfies a quadratic equation over ${\rm GF}(p).$ Hence ${\rm GF}(p^{2})$ contains an element of multiplicative order $5$, so that $5$ divides $p^{2}-1$ and $p \equiv \pm 1$ (mod $5$).
More detail: We know that $ \alpha = \omega +\omega^{-1}$ is a root of $x^{2}+x-1$ as above, and lies in ${\rm GF}(p).$ Now $(\omega - \omega^{-1})^{2}  = -2 - (1 + \omega + \omega^{-1}) = -3 - \alpha.$ Hence $\omega - \omega^{-1}$ lies in a quadratic extension (at most) of ${\rm GF}(p).$ Since $\omega+ \omega^{-1} \in {\rm GF}(p),$ we see that $\omega$ itself lies in a (at most) quadratic extension  on ${\rm GF}(p).$ 
To treat the case $p = 2,$ note that $2$ is not a quadratic residue (mod $5$) by inspection.
Later note in response to question of PI: I think this approach may generalize, but it seems to stray into the realm of Gauss sums, and I have not worked through all 
the details: let $p,q$ be odd primes, and let $\omega$ be a primitive $q$-th root of unity in $\overline{{\rm GF}(p)}.$ Consider $\sigma = \sum_{i=0}^{\frac{q-3}{2}} \omega^{p^{i}}.$ Suppose that $p$ is a quadratic residue (mod $q$). Then $p^{\frac{q-1}{2}} \equiv 1 $ (mod $q$). Hence $\sigma^{p} = \sigma$ and $\sigma \in {\rm GF}(p).$ Conversely, if $p$ is not a quadratic residue (mod $p$), then $\sigma^{p} \neq \sigma$ as $p^{\frac{q-1}{2}} \not \equiv 1 $ (mod $q$). 
A: One direction; if $(5|p) = 1,$ then $(20|p) =1.$ So, there is a solution to
$$  20 \equiv b^2 \pmod {4p},  $$
where if we first found $b$ odd we switch to $p-b$ for it to become even.
or $$ 20 = b^2 - 4 p t.  $$
So, we have the indefinite binary quadratic form $$ \langle p,b,t \rangle.  $$
More on its way...
Alright, discriminant 20 has class number one, any such form is $SL_2 \mathbb Z$ equivalent to $x^2 - 5 y^2.$ What this means is that there is an integer expression
$$  x^2 - 5 y^2 = p.  $$
Now, we find
$$ x^2 \equiv p  \pmod 5.   $$
Which says that $(p|5)=1.$
EXTRA: i think this works; if $(q|5)=1,$ some form in the principal genus, the same as $u^2 - q v^2,$ represents $5.$ The form is rationally equivalent, without essential denominator (Siegel's phrase), to $u^2 - q v^2,$ so we have rational $r^2 - q s^2 = 5,$ clear denominators to get integer $x^2 - q y^2 = 5 z^2. $ But then 
$x^2 -5 z^2 = q y^2  $ and $x^2 \equiv 5 y^2 \pmod q,$ so $(5|q)=1.$
Alright, needs to be checked for hidden reciprocity, I suppose. Kap used to say that the totality of the theory of binary forms was equivalent to quadratic reciprocity. May be something to that.
There may be some separation needed depending on $q \pmod 4.$ Short theorem in Mordell's book that $x^2 - q y^2$ and $-x^2 + q y^2$ are equivalent when $q \equiv 1 \pmod 4,$ but they are distinct otherwise, and that may matter... When $q \equiv 1 \pmod 4,$ we can descend to discriminant $q$ with principal form $x^2 + x y - \frac{p-1}{4}y^2$ and guarantee a single genus, although not always a single class.
A: Not an answer, but might be useful. In section 6.2 of:
Ireland and Rosen: A Classical Introduction to Modern Number Theory
they use some basic algebra and a  primitive eighth root of unity to derive the quadratic character of 2, and then in exercise 8 at the end of the chapter, they ask the reader to do something similar to derive the quadratic character of -3 (I did the exercise some years ago, but no longer have my notes). I suspect something similar could be done with 5.
