This is Lemma 4.8 (Exercise 4.4) in Elements of Finite Model Theory by Libkin.
Assume that $h\colon N_r(\overline{a}) \rightarrow N_r(\overline{b})$ is an isomorphism between the neighborhoods of $r$-distance (where distance is in the Gaifman graph) induced by the tuples $\overline{a}$, $\overline{b}$ in structures $A$, $B$ respectively. Then show that for $d\leq r$, the restriction of $h$ to $N_d(\overline{a})$ is an isomorphism $N_d(\overline{a}) \rightarrow N_d(\overline{b})$.
Clearly, it would suffice to show that for any element $x$ of distance $m$ away from $\overline{a}$, with $m\leq d$, $h(x)$ is of distance $m$ away from $\overline{b}$. For distance $0$ this is easy, as distance $0$ implies that $x$ is one of the components of $\overline{a}$, but $h$ maps $\overline{a}$ to $\overline{b}$ and this is enough. I'm having trouble with showing this for other $m$, though.
Suppose for example that the distance is one. Then $d(a_i, x) = 1$ for some $a_i$, i.e., $R^A(\overline{t})$ holds for some tuple $\overline{t}$ containing $a_i$ and $x$. If all components of $\overline{t}$ were in $N_r(a)$, then $R^b(h(\overline{t}))$ would hold and we would obtain the edge $E(b_i, h(x))$. But I don't know that all components of $t$ are less than $r$ away from $\overline{a}$, and quantifying hasn't seemed to help either.
Let's show by induction on $m$ that for $0\leq m \leq d\leq r$, if $x\in N_m(\overline{a})$, then $h(x)\in N_m(\overline{b})$.
You proved the base case in your question: The elements of $N_0(\overline{a})$ are the components of $\overline{a}$, which are mapped to the components of $\overline{b}$ by $h$.
Now suppose $m+1\leq d$ and $x\in N_{m+1}(\overline{a})$. If $x\in N_m(\overline{a})$, we're done by induction. Otherwise, $x$ has a neighbor $y$ in $N_{m}(\overline{a})$. So there exists a relation $R$ and a tuple $\overline{t}\in R^A$ such that $\overline{t}$ contains both $x$ and $y$. Since $y\in N_{m}(\overline{a})$, every component of $\overline{t}$ is in $N_{m+1}(\overline{a})\subseteq N_{r}(\overline{a})$, so $h(\overline{t})\in R^B$. It follows that $h(x)$ is adjacent to $h(y)$. By induction, $h(y)\in N_m(\overline{b})$, so $h(x)\in N_{m+1}(\overline{b})$, as desired.