Numerical experiments suggest that $\binom{2m}{m + k}\cdot\frac{3m - 1 - 2k^2}{2m - 1}$ is integer for all $-m \le k\le +m$. It means that expression evaluation could be implemented very efficiently, only using integer addition and multiplication.

However, I've failed to derive computationally efficient expression so far. The two ideas I have are linear combination of binomials, and recursion -- but more insight is needed to go further.