Here is a combinatorial proof.
It is more convenient to prove the equivalent formula (obtained by setting $n=m+2j$)
$$\sum_k \binom{k}{j}\binom{m+2j}{2k}=2^{m-1}\frac{m+2j}{m+j}\binom{m+j}{j}.\tag{$*$}$$
To motivate the proof we first prove the closely related but slightly easier
formula
$$\sum_k \binom{k}{j}\binom{m+2j+1}{2k+1} = 2^m\binom{m+j}{j}.\tag{1}$$
Let us first give a generating function proof of $(1)$. We start by multiplying the summand by $x^j y^m$ and summing on $j$ and $m$. We find that
$$
\sum_{j,m}\binom{k}{j}\binom{m+2j+1}{2k+1} x^j y^m = \frac{(x+y^2)^k}{(1-y)^{2k+2}}
$$
and that
$$\sum_{k=0}^\infty \frac{(x+y^2)^k}{(1-y)^{2k+2}}=\frac{1}{1-x-2y} = \sum_{j,m}2^m\binom{m+j}{j}x^j y^m.\tag{2}$$
It is not hard to find objects counted by $2^m\binom{m+j}{j}$. We need to interpret $(x+y^2)^k/(1-y)^{2k+2}$ as counting some of these objects, and this is what the following proof does.
Let $S$ be the set of words in the the letters $x, y_1, y_2$ containing $j$ occurrences of $x$ and a total of $m$ occurrences of $y_1$ and $y_2$. There are $\binom{m+j}{m}$ words with $j$ occurrences of $x$ and $m$ occurrences of $y$. Each $y$ can be replaced with $y_1$ or $y_2$ so there are $2^m\binom{m+j}{m}$ words in $S$.
Now we count the words in $S$ in a different way. Let us define a stopper of a word in $S$ to be an occurrence of either $x$ or $y_2y_1$, and let us call the subwords before, between, and after the stoppers segments, so a word with $k$ stoppers has $k+1$ segments. Thus each segment is of the form $y_1^a y_2^b$, where $a$ and $b$ are nonnegative integers. For example, the word $y_1 y_2 x y_2 y_1 y_2 y_2x$ has three stoppers, $x$, $y_2y_1$, and $x$, and four segments, $y_1y_2$, $\varnothing$, $y_2y_2$, and $\varnothing$. (Here $\varnothing$ denotes the empty word.)
Let us count words in $S$ with $k$ stoppers (and thus $k+1$ segments). We must have $k\ge j$, since every $x$ is a stopper. Then there are $k-j$ stoppers of the form $y_2y_1$ so there are $m-2(k-j)$ occurrences of $y_1$ and $y_2$ among the $k+1$ segments. The segments are of the form $y_1^{a_0}y_2^{b_0},y_1^{a_1}y_2^{b_1},\dots,y_1^{a_k}y_2^{b_k}$, where $a_0+b_0+\cdots +a_k+b_k=m-2(k-j)$. The number of solutions in nonnegative integers of this equation is $\binom{m+2j+1}{2k+1}$
(since for fixed $r$ and $s$ the number of nonnegative integer solutions of $c_1+c_2+\cdots +c_r = s$ is $\binom{r+s-1}{s}=\binom{r+s-1}{s-1}$).
Once the $a_i$ and $b_i$ are determined, the $k$ slots for the stoppers are fixed, and
we may decide which are $x$ and which are $y_2y_1$ in $\binom{k}{j}$ ways. Thus the number of elements of $S$ is
$$
\sum_k \binom{k}{j}\binom{m+2j+1}{2k+1},
$$
which must also be equal to $2^m\binom{m}{j}$.
To prove the original identity $(*)$, we replace $2k+2$ with $2k+1$ in the denominator of the left side of $(2)$. This corresponds to counting only those words in $S$ for which $a_0=0$, i.e., the words in $S$ that do not start with $y_1$. The number of solutions of $a_0+b_0+\cdots +a_k+b_k=m-2(k-j)$ with $a_0=0$ is $\binom{m+2j}{2k}$, so the number of these words is the left side of $(*)$. But (assuming $j$ and $m$ are not both 0) the number of words in $S$ that start with $y_1$ is $2^{m-1}\binom{m+j-1}{j}$, so the number of words in $S$ that do not start with $y_1$ is
$$2^j\binom{m+j}{j} -2^{m-1}\binom{m+j-1}{j} = 2^{m-1}\frac{m+2j}{m+j}\binom{m+j}{j}.$$
