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.