My aim is showing the equivalence of two discrete Sobolev norms. On $\mathbb{Z}^d$, $d\ge 2$, one defines the discrete derivative in the direction of the coordinate vector $\vec e_j$ as
$$
D_{j}f(x):=f(x+\vec e_j)-f(x)
$$
with the convention that $D_{-j}f(x):=f(x-\vec e_j)-f(x).$ The discrete Sobolev norm is
$$
\Vert f\Vert_1^2:=\sum_{\ell=0}^2 \,\sum_{i_1,\,\ldots,.\,i_\ell=\pm 1,\ldots,\,\pm d}\,\sum_{x\in \mathbb Z^d}\left|D_{i_1}\ldots D_{i_\ell}f(x)\right|^2,\,\quad f:\mathbb Z^d\to \mathbb R.
$$
There is also the possibility of defining a norm as follows:
$$
\Vert f\Vert_2^2:=\Vert \nabla_2 f\Vert_{\ell^2}^2:=\sum_{i_1,\,i_2=\pm 1,\,\ldots,\,\pm d}\, \sum_{x\in \mathbb Z^d}\left|D_{i_1} D_{i_2}f(x)\right|^2.
$$
Obviously $\Vert f\Vert_2\le \Vert f\Vert_1$. As for the reverse inequality, I can show it under the following assumption: suppose $f$ is a function of finite $\Vert\cdot\Vert_1$-norm and call $A:=\left\{ x\in\mathbb Z^d:\,f(x)=0\right\}.$ If there exists $M<+\infty$ with $\sup_{x\in \mathbb Z\setminus A}\mathrm{dist}(x,\,A)\le M$, then there exists $C=C(M,\,d,\,\sup_x \left|f(x)\right|)\in(0,\,+\infty)$ with $\Vert f\Vert_1\le C\Vert f\Vert_2$. The proof basically relies on the fact that I can bound the $\ell^2$ norms of $f$ and $\nabla f$ using telescopic sums starting from a point where $f(x)$ is zero (so of length no bigger than $M$) and then using integration by parts.

My question is: can the bound be improved so that $C$ doesn't depend on $M$? I am not interested in the sharpest $C$ possible, but rather in removing the assumption on the existence of $M$ finite. Is the equivalence true at all in $\mathbb Z^d$ in this fashion?

The two norms are not equivalent for functions with finite $\|\cdot\|_1$ norm. Let $L>0$ be a large integer and let $f$ be the characteristic function of the cube $[0,L]^d\subset\mathbb Z^d$. In the following calculations I do not care about constants, but only about scaling in $L$.

First, $\|f\|_{\ell^2}\approx L^d$. The gradient of $f$ is supported at the boundary of cube (volume $\approx L^{d-1}$) and the absolute values of the derivatives are bounded by one. Therefore $\|\nabla f\|_{\ell^2}\approx L^{d-1}$. Similarly the second derivatives of $f$ are nonzero only at the boundary of the cube and the absolute values are bounded by one, so that $\|D^2 f\|_{\ell^2}\approx L^{d-1}$. Therefore $\|f\|_1\gtrsim L\|f\|_2$, so taking $L$ large shows that $\|f\|_1\lesssim\|f\|_2$ is not possible.

As a side remark, linear and constant functions have zero $\|\cdot\|_2$ norm but infinite $\|\cdot\|_1$ norm. This gives a reason to believe that approximating such a function might give a counterexample to the estimate you wanted to prove. I hope you can see the idea of approximating the constant function $f\equiv1$ in the proof above.