Yes, such a directed graph exists, with a "quickly" computable path of length $O(\log|n-m|)$ from $m$ to $n$ for any distinct integers $m,n$.
I'll first construct a digraph with this property but with each vertex having out-degree at most $8$, then show how to get from it a digraph of out-degree $2$.
Denote by $v(x)$ the $2$-adic valuation of the integer $x$, which is the unique integer $e \geq 0$ such that $x/2^e$ is an odd integer; conventionally $v(0) = \infty$.
The graph edges emanating from $x$ will be as follows. If $x$ has valuation $e>0$ then
$$
x \rightarrow x \pm 1, \phantom+ x \pm 2^{e-1}, \phantom+ x \pm 2^e, \phantom+ x \pm 3\cdot 2^e.
$$
If $x$ is odd, omit $x \pm 2^{e-1}$ so $x$ goes only to $x \pm 1$ and $x\pm 3$. If $x=0$ then $x\mapsto \pm 1$ only.
Then:
(i) For each $e \geq 0$, the integers of valuation $e$ constitute an arithmetic progression of common difference $2^{e+1}$. We can get from such $x$ to $x \pm 2^{e+1}$ in two steps: if $e=0$ then add or subtract $1$ twice; if $e>0$ then add or subtract $2^{e-1}$ and then $3 \cdot 2^{e-1}$.
(ii) If $v(x) = e$ and $|n-m| \leq 2^e$ we can get from $m$ to $n$ in at most $2 \phantom. \log_2 |n-m| + 1$ steps. Indeed if $|n-m| = 2^e$ one step suffices, so assume $|n-m| < 2^e$ and then $|n-m| \in [2^d, 2^{d+1})$ with $d < e$. By symmetry we may assume $n>m$. Then
$$
m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d
$$
in $d+1$ steps, and then in a further $d - v(n)$ steps we reach $n$ by writing
$$
n = m + 2^d + 2^{d-1} \pm 2^{d-2} \pm 2^{d-3} \pm \cdots \pm 2^{d-v(n)}.
$$
(iii) If $v(m) = e < f$, and $n$ is the integer of valuation exactly $f$ that's nearest to $m$, then we can get from $m$ to $n$ in $f-e$ steps. At the $i$-th step, add either $\pm 2^{e+i-1}$ or $\pm 3 \cdot 2^{e+i-1}$ to reach a number of valuation exactly $e+i$; there are two choices, so take the one closer to $n$. The distance to $n$ always stays below $2^f$ so at step $f-e$ we hit $n$.
(iv) Finally, suppose $m$ is odd and $|n-m| \in [2^k, 2^{k+1})$. Find $n'$ of valuation $k$ such that $|n-n'| \leq 2^k$. Thus $|m-n'| < 3 \cdot 2^k$. By (iii), in $k$ steps we get from $m$ to some $n_1$ such that $|m-n_1| < 2^k$ and $v(n_1) = k$. So either $n_1=n'$ or $n_1 = n' \pm 2^{k+1}$, and in the latter case we reach $n'$ in a further two steps using (i). Then in at most $2k+1$ further steps we reach $n$ using (ii).
We are done, in a total of $3 \phantom. \log_2 |n-m| + O(1)$ steps, because if $m$ is not odd then we can use our first step to move to the odd number $m \pm 1$ closer to $n$.
Now to get from out-degree $8$ down to $2$: for each $x \in {\bf Z}$ choose $f_i(x)$ for $i=0,1,2,\ldots,7$ so that $\{f_0(x),f_1(x),f_2(x),\ldots,f_7(x)\}$ is the set of integers reachable from $x$ (with repetitions if $x$ is odd or zero). Define a new graph of out-degree $2$ as follows: write every integer as $8x+i$ for some $x \in \bf Z$ and $i\in\{0,1,2,\ldots,7\}$, and then $8x+i \rightarrow 8f_i(x)$ and $8x+i \rightarrow 8x+i'$ where $i'=0$ if $i=7$ and $i'=i+1$ otherwise. That is, we partition $\bf Z$ into directed $8$-cycles, which consumes only one outgoing edge per integer and leaves us with $8$ further edges per cycle to assign as we wish, letting us use our graph of out-degree $8$. Each step of our algorithm then expands to at most $8$, because we might have to take as many as $7$ steps cycling around until we reach the correct $i$ to make the next step in our original graph, and then at the end we might still have to spend an extra $7$ steps to reach the target $n$ within its cycle. But that's still at most $24 \phantom. \log_2 |n-m| + O(1)$ steps, and still with an explicit and "quick" algorithm.
[EDIT we can reduce $3 \phantom. \log_2 |n-m| + O(1)$ to $\frac52 \log_2 |n-m| + O(1)$ by compressing
$$m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d$$
to
$$m \rightarrow m + 1 \rightarrow m + 4 \rightarrow m+16 \rightarrow \cdots \rightarrow m+2^d,$$
and there's probably another multiple of $\log_2|n-m|$ to be saved by permuting
$f_0(x),f_1(x),f_2(x),\ldots,f_7(x)$ to reduce the number of steps spent within directed $8$-cycles.]
