Some general remarks. There is a family of linear operators $\phi_{a,d}$ which, given a generating function $f(x) = \sum f_n x^n$, returns the generating function $\sum f_{an+d} x^n$. Observe that, for $\zeta$ a primitive $a^{th}$ root of unity,
$$f(\zeta^k x) = \sum_{i=0}^{a-1} \zeta^{ki} \phi_{a,i}(f(x)).$$
This is precisely the discrete Fourier transform matrix of order $a$, and inverting it tells us how to write down these operators $\phi_{a,d}$ explicitly and in particular to compute all sums of the form $\displaystyle \sum {n \choose ak+d}$.
In this particular case there is a dirty trick I like to employ. Given a generating function $f(x) = \sum f_n x^n$, the generating function $g(x) = \sum g_n x^n$ where
$$g_n = \sum_{k=0}^{n} {n \choose k} f_k$$
satisfies
$$g(x) = \frac{1}{1 - x} f \left( \frac{x}{1 - x} \right).$$
One may deduce this either by performing and inverting a Laplace transform or combinatorially. Either way, it allows us to evaluate the sums $\displaystyle \sum {n \choose ak+d}$ by setting $f(x) = \frac{x^d}{1 - x^a}$.