Here are some observations, though not quite a combinatorial proof of the identity in question.

Let $A(m,n)$ be the value of the sums. Let $B(m,n)=(-1)^m A(m, m+n)$. Then $B(m,n)$ is nonnegative for all $m$ and $n$ (and is zero only if $m$ is odd and $n=0$).

It's not too hard to give a combinatorial interpretation to $B(m,n)$. It's easy to show that $B(m,n)$ has the simple generating function
$$
\beta(x,y) = \sum_{m,n=0}^\infty B(m,n) x^m y^n = \frac{1}{(1+x)(1-x-y)}.
$$
It follows that $B(m,n)$ satisfies the Pascal-like recurrence
$$B(m,n)=B(m-1, n) + B(m,n-1)$$
for $m\ge0$ and $n>0$ with initial values $B(-1,n)=0$, $B(m,0)=1$ for $m$ even and $B(m,0)=0$ for $m$ odd.
We can see that $B(m,n)$ is nonnegative by writing the generating function as
$$
\beta(x,y)=\frac{1-x}{(1-x^2)(1-x-y)}=\frac{1}{1-x^2}\left(1+\frac{y}{1-x-y}\right),
$$
or more simply,
$$\sum_{m=0}^\infty \sum_{n=1}^\infty B(m,n) x^m y^n = \frac{y}{(1-x^2)(1-x-y)},$$
which gives the simpler formula
$$B(m,n) = \sum_{0\le i\le m/2} \binom{m+n-2i-1}{n-1}$$
for $n>0$. From these generating functions we see that that $B(m,n)$ is the number of lattice paths from $(0,0)$ to $(m,n)$, with unit east and north steps, that start with an even number of east steps.

The OP's second sum gives
$$
B(m,n) = \sum_{j=0}^m (-1)^{m-j}\binom{n+j}{j}=\sum_{j=0}^m (-1)^j \binom{n+m-j}{m-j}.
$$
This comes from expanding $\beta(x,y)$ as
$$\frac{1-x+x^2-x^3+\cdots}{1-x-y}$$
and is easy to interpret combinatorially: $\binom{n+m-j}{m-j}$ is the number of paths from $(j,0)$ to $(m,n)$, or equivalently the number of paths from $(0,0)$ to $(m,n)$ that start with $j$ east steps (possibly followed by more east steps), or in other words, the number of paths from $(0,0)$ to $(m,n)$ that pass through $(j,0)$. Then for $j$ even, $\binom{n+m-j}{m-j}-\binom{n+m-j-1}{m-j-1}$ counts paths from $(0,0)$ to $(m,n)$ that start with $j$ east steps followed by a north step. Add this over all even $j\le m$ gives all the paths counted by $B(m,n)$.

The identity in question (with $n$ replaced $m+n$ and the order of the summations reversed) may be written as
$$
\sum_{i=0}^m (-2)^i\binom{m+n+1}{m-i}
=\sum_{j=0}^m (-1)^j \binom{m+n-j}{m-j}.
$$
This is the case $t=-2$ of the identity
$$
\sum_{i=0}^m t^i\binom{m+n+1}{m-i}=
\sum_{j=0}^m (1+t)^j\binom{m+n-j}{m-j}.
\tag{1}
$$
We can give a combinatorial interpretation of $(1)$, but I don't see that setting $t=-2$ has a simple combinatorial interpretation (though what I described above is a combinatorial interpretation of setting $t=-2$ in the right side).
The combinatorial interpretation of $(1)$ is made clearer by looking at the generating function for $(1)$, which is
$$\frac{1}{(1-(1+t)x)(1-x-y)}.$$
The right side of $(1)$ is obtained by expanding this in the most straightforward way; the left side is obtained by expanding it as
$$
\frac{1}{(1-x)^2} \frac{1}{1-tx/(1-x)}\frac{1}{1-y/(1-x)}=
\sum_{i,n}\frac{(tx)^i y^n}{(1-x)^{i+n+2}}.
$$

To interpret the right side of $(1)$, we consider paths from $(0,0)$ to $(m,n)$, which are “cut” at some point $(j,0)$ on the $x$-axis (so they must start with at least $j$ east steps) and some subset of the first $j$ (east) steps are “marked” and weighted by $t$. It is clear that the contributions from the paths cut at $(j,0)$ is $(1+t)^j\binom{m+n-j}{m-j}$: each of the first $j$ (east) steps contributes 1 or $t$, and $\binom{m+n-j}{m-j}$ counts paths from $(j,0)$ to $(m,n)$. For the left side, given such a cut and marked path, with $i$ marked east steps, we change each marked east step to a north step and insert an additional north step after the $j$th step, obtaining a path with $m-i$ east steps and $n+i+1$ north steps, and these are counted by $\binom{m+n+1}{m-i}$. It is easy to see that this transformation is bijective—to go back we change the first $i$ north steps to marked east steps, set $j$ to the number of steps before the $(i+1)$st north step, and delete the $(i+1)$st north step.

It may be noted that $(1)$ is a special case of a $_2F_1$ linear transformation; a generalization can be obtained easily be expanding
$$\frac{1}{(1-(1+t)x)^a (1-x-y)^b}$$
in the same two ways.