An alternative proof that is much the same as Thomas Andrews':
Recall that the Legendre symbol is a multiplicative quadratic character on $\mathbb{F}_p$. In particular, by orthogonality, we have
$ \sum_{x \in \mathbb{F}_p} \left( \frac{x}{p} \right) = 0. $
This statement follows easily from the fact that there are just as many residues as nonresidues in $\mathbb{F}_p$ when $p$ is odd, but I think it is important to understand the more general structure. We wish to find a value for
$ \sum_{k \in \mathbb{F}_p}\left(\frac{k^2 - d}{p} \right). $
We have
$ \sum_{k \in \mathbb{F}_p} \left(\frac{k^2 - d}{p} \right) = \sum_{y \in \mathbb{F}_p} \left(\frac{y}{p}\right)N(y), $
where we made the Change of Variables $y = k^2 - d$, and
$ N(y) = \# \{y \in \mathbb{F}_p : y = k^2 - d\}. $
Note that $y = k^2 - d$ has a solution if and only if $y + d$ is a square. Hence,
$ N(y) = 1 + \left( \frac{y+d}{p} \right). $
Then, we see that
$\begin{align} \sum_{y \in \mathbb{F}_p} \left( \frac{k^2 - d}{p} \right) &= \sum_{y \in \mathbb{F}_p} \left( 1 + \left( \frac{y+d}{p} \right) \right) \left(\frac{y}{p} \right). \end{align}$
Finally, the change of variables $j \to y - d$ yields what we want:
$ \sum_{j \in \mathbb{F}_p} \left(1 + \left( \frac{j}{p} \right) \right) \left( \frac{j - d}{p} \right). $
The advantage to this method is that it required basically no ingenuity. Applying the change of variables made it clear the quantity we wanted to evaluate (which was $N(y)$ using my notation), and this was straight-forward using your own observations.