Well, if algebra doesn't help, let's try good old complex analysis. Put $u=k-j+m$, $s=k+m$ and rewrite the sum as $$ \sum_{u\ge 1}2^u\frac{u!(u-1)!}{(2u)!}[x^m]\sum_{s\ge u}2^{-2s}{2s\choose s}x^s(1-\frac 1x)^m $$ where $[x^m]F(x)$ is the $m$-th Laurent coefficient of $F$ at $0$.

Now we can at least recognize the coefficients. The sum in $s$ is just the truncated Taylor sum for $\frac 1{\sqrt{1-x}}$ and $2^u\frac{u!(u-1)!}{(2u)!}=\int_0^1{[2t(1-t)]^u}\frac{dt}{t}$. Recalling that the truncation of analytic functions to high frequences is just $z^uP_+z^{-u}$ where $P_+$ is the Cauchy integral, and that the coefficient at the $m$-th power can be obtained by integration against $z^{-m}$ over a circle, we can write this monster as $$ \int_0^1 \frac{dt}{t}\sum_{u\ge 1}[2t(1-t)]^u\oint\oint \frac{z^u z^{-2m}(z-1)^m}{\zeta^u\sqrt{1-\zeta}(1-\frac z\zeta)}dm(z)dm(\zeta) $$ with circular integral taken over the circles of radii less than $1$ with the radius for $z$ smaller than that for $\zeta$ ($m$ is the averaging measure here, so the integrals are just the averages over the corresponding circles). Now, summing over $u$, we get $$ \int_0^1 \frac{dt}{t}\oint\oint\left(\frac{1}{1-2t(1-t)\frac z\zeta}-1\right) \frac{z^{-2m}(z-1)^m}{\sqrt{1-\zeta}(1-\frac z\zeta)}dm(z)dm(\zeta) $$ Now $(\frac{1}{1-pw}-1)\frac 1{1-w}=\frac p{1-p}(\frac1{1-w}-\frac1{1-pw})$ Thus, using the Cauchy formula again and integrating over $\zeta$, we convert it into $$ \int_0^1 \frac{2(1-t)dt}{1-2t(1-t)}\oint\left(\frac{1}{\sqrt{1-z}}-\frac{1}{\sqrt{1-2t(1-t)z}}\right) {z^{-2m}(z-1)^m}dm(z) $$ The integral in $t$ is an elementary function of $z$ analytic near the origin (have a nice CAS!) The claim that the integral is $0$ for all $m$ is equivalent to the claim that after change of variable $w=\frac z{\sqrt {1-z}}$ all the Taylor coefficients of the new integrand in $w$ with even indices are $0$, i.e., the new integrand is an odd function in $w$ (have more nice CAS!). Whether true or false, it is verifiable now. So, I'll stop here -:).

Well, if algebra doesn't help, let's try good old complex analysis. Put $u=k-j+m$, $s=k+m$ and rewrite the sum as $$ \sum_{u\ge 1}2^u\frac{u!(u-1)!}{(2u)!}[x^m]\sum_{s\ge u}2^{-2s}{2s\choose s}x^s(1-\frac 1x)^m $$ where $[x^m]F(x)$ is the $m$-th Laurent coefficient of $F$ at $0$.

Now we can at least recognize the coefficients. The sum in $s$ is just the truncated Taylor sum for $\frac 1{\sqrt{1-x}}$ and $2^u\frac{u!(u-1)!}{(2u)!}=\int_0^1{[2t(1-t)]^u}\frac{dt}{t}$. Recalling that the truncation of analytic functions to high frequences is just $z^uP_+z^{-u}$ where $P_+$ is the Cauchy integral, and that the coefficient at the $m$-th power can be obtained by integration against $z^{-m}$ over a circle, we can write this monster as $$ \int_0^1 \frac{dt}{t}\sum_{u\ge 1}[2t(1-t)]^u\oint\oint \frac{z^u z^{-2m}(z-1)^m}{\zeta^u\sqrt{1-\zeta}(1-\frac z\zeta)}dm(z)dm(\zeta) $$ with circular integral taken over the circles of radii less than $1$ with the radius for $z$ smaller than that for $\zeta$ ($m$ is the averaging measure here, so the integrals are just the averages over the corresponding circles). Now, summing over $u$, we get $$ \int_0^1 \frac{dt}{t}\oint\oint\left(\frac{1}{1-2t(1-t)\frac z\zeta}-1\right) \frac{z^{-2m}(z-1)^m}{\sqrt{1-\zeta}(1-\frac z\zeta)}dm(z)dm(\zeta) $$ Now $(\frac{1}{1-pw}-1)\frac 1{1-w}=\frac p{1-p}(\frac1{1-w}-\frac1{1-pw})$ Thus, using the Cauchy formula again and integrating over $\zeta$, we convert it into $$ \int_0^1 \frac{2(1-t)dt}{1-2t(1-t)}\oint\left(\frac{1}{\sqrt{1-z}}-\frac{1}{\sqrt{1-2t(1-t)z}}\right) {z^{-2m}(z-1)^m}dm(z) $$ The integral in $t$ is an elementary function of $z$ analytic near the origin (have a nice CAS!) The claim that the integral is $0$ for all $m$ is equivalent to the claim that after change of variable $w=\frac z{\sqrt {1-z}}$ all the Taylor coefficients of the new integrand in $w$ with even indices are $0$, i.e., the new integrand is an odd function in $w$ (have more nice CAS!). Whether true or false, it is verifiable now. So, I'll stop here -:).

Edit: It is true. After some moderately tedious computations, it boils down to the fact that $\operatorname{arctan}\sqrt{1-z}-\frac\pi 4$ is an odd function of $w=\frac{z}{\sqrt{1-z}}$, which, believe it or not, is correct. I think you have already checked it using those cute CAS programs, which I haven't on my old laptop, so I'm not posting the details.

Of course, the challenge to find a combinatorial interpretation of this formula still remains.