A summation identity

Here is a very different kind of answer than what you want. This is a sum of hypergeometric terms, and therefore in principle your identity is algorithmic to verify.

If we let $S(n)$ be your sum, then Zeilberger's algorithm (with, say, SumTools[Hypergeometric][Zeilberger](S, n, m, E) in Maple) returns the result $$ [E + 4,\ {\frac {m \left( 2\,m-1 \right) \left( -1 \right) ^{m} \left( 2\,n+2\,m \right) !\, \left( 8\,n+6 \right) }{ \left( -n+m-1 \right) \left( n+m \right) !\, \left( n-m \right) !\, \left( 2\,m \right) !\, \left( 2\,{n}^{2}+3\,n+1 \right) }}], $$ where $E$ is the shift operator $ES(n) = S(n + 1)$. This signifies that $S(n)$ satisfies the recurrence $(E + 4) S(n) = 0$, i.e., $S(n + 1) = -4S(n)$. (The second part is to "verify" the results of the algorithm, if you were so inclined.) Since it is easy to check that $S(0) = 1$, it follows that $S(n) = (-4)^n$ for $n \geq 0$.

---

Here's a more human approach, though still not "directly" evaluating the sum. I liberally use generating functions - see generatingfunctionology for a nice introduction.

Note that your sum is $$S(n) = \sum_{k = 0}^n (-1)^k {2(n + k) \choose n + k} {n + k \choose n - k} = \sum_{k \leq n} (-1)^k {2(n + k) \choose n + k} {n + k \choose n - k}$$ for $n \geq 0$. If we shift the summation variable back by $n$, then $$S(n) = \sum_{k \leq 2n} (-1)^{k - n} {2k \choose k}{k \choose 2n - k}.$$

There is one obvious simplification to try here: $(-1)^k {2k \choose k} = 4^k {-1/2 \choose k}$, which gives

$$S(n) = (-1)^n \sum_{k \leq 2n} 4^k {-1/2 \choose k}{k \choose 2n - k}.$$

The remaining hard part is the sum. The $2n$ is unimportant now (only $2n$ appears in the sum, never $n$ by itself), so let's define

$$R(n) = \sum_{k \leq n} 4^k {-1/2 \choose k} {k \choose n - k}.$$

If we have $R(n)$, then $S(n) = (-1)^n R(2n)$. [There is probably an easy way to evaluate $R(n)$, but I haven't found it yet.]

Let's stop thinking so hard, define $$R(x) = \sum_{n \geq 0} R(n) x^n,$$ and blindly manipulate some sums:

\begin{align*} R(x) &= \sum_{n \geq 0} \sum_{k \leq n} 4^k {-1/2 \choose k} {k \choose n - k} x^n \\ &= \sum_{k \geq 0} \sum_{n \geq k} 4^k {-1/2 \choose k} {k \choose n - k} x^n \\ &= \sum_{k \geq 0} 4^k {-1/2 \choose k} \sum_{n \geq k} {k \choose n - k} x^n \\ &= \sum_{k \geq 0} 4^k {-1/2 \choose k} \sum_{n \geq 0} {k \choose n} x^{n + k} \\ &= \sum_{k \geq 0} 4^k {-1/2 \choose k} x^k (1 + x)^k \\ &= \sum_{k \geq 0} [4x(1 + x)]^k {-1/2 \choose k} \\ &= (1 + 4x(1 + x))^{-1/2} \\ &= \frac{1}{1 + 2x} \\ &= \sum_{n \geq 0} (-2)^n x^n. \end{align*}

Therefore $R(n) = (-2)^n$, which finally gives $S(n) = (-1)^n R(2n) = (-4)^n$.