Note that $r - 1 = \left\lfloor \log_2(k_s) \right\rfloor \; \rightarrow \; r - 1 \le \log_2(k_s) \lt r \; \rightarrow \; 2^{r-1} \le k_s \lt 2^{r}$. Thus, in the base $2$ expansions, $k_s$ has a $1$ coefficient for the $2^{r-1}$ term, but $k_s + 2^{r-1}$ has a carry of the $2^{r-1}$ term, meaning its coefficient is $0$. Thus, by Lucas's theorem, those coefficients give $\binom{0}{1} = 0$ for the $2^{r-1}$ term, meaning the congruence product, modulo $2$, is $0$.
FYI, Kummer's theorem can also be used to prove this since there's a carry when adding $k_s$ and $2^{r-1}$ in base $2$, as I explained earlier. In addition, since there's only one carry, this theorem shows that $\binom{k_s + 2^{r-1}}{k_s}$ has just one factor of $2$.
I believe your conjecture is true. Here is an attempted proof that's pretty close to working but ends up relying on a famous number theory conjecture.
First note: If $p$ is prime, then $p | n!$ if and only if $n \ge p$.
Let $r(n,k) = \frac{n(n-1)}{2} + 3 + k$ and $s(n,k) = \lfloor \frac{n-1}{2} \rfloor + 1 + k$, so that $a(k,n) = \binom{r(n,k)}{s(n,k)}$. Among the coefficients being GCD'd to compute $b_n$, the smallest $r$ will be $r(n,0) = \frac{n(n-1)}{2} + 3$; the largest $s$ is $s(n,n-1) = \lfloor \frac{n-1}{2} \rfloor + n$; and $r-s$ will be the same across all of the binomial coefficients in question. This means the conjecture will be proved if we can show there's some prime $p$ satisfying
$$\begin{align}
\left\lfloor \frac{n-1}{2} \right\rfloor + n &< p \\
\frac{n(n-1)}{2} - \left\lfloor \frac{n-1}{2} \right\rfloor + 2 &< p \\
p &\le \frac{n(n-1)}{2} + 3 \\
\end{align}$$
We actually have $\left\lfloor \frac{n-1}{2} \right\rfloor + n \le \frac{n(n-1)}{2} - \left\lfloor \frac{n-1}{2} \right\rfloor + 2$ for all $n \ge 1$, so we can ignore the first inequality above.
Let $x(n) = \frac{n(n-1)}2$. Then $\left\lfloor \frac{n-1}{2} \right\rfloor \le \sqrt{x/2}$, and for my proof to work I need to find $p$ with $x-\sqrt{x/2}+2 < p \le x+3$.
This last statement is true for all the $n$ I could quickly check. Also, the statement being true for sufficiently large $x$ (i.e. sufficiently large $n$) is basically Legendre's conjecture but a little stronger due to the fixed constant. See also Wikipedia's sections on upper bounds for prime gaps and conjectures related to prime gaps for more reading material. Basically, people in the field think the conjecture is probably true, but cutting edge number theory methods have been sloooowly chipping away at the problem by proving slightly better bounds over time.
Even if the conjecture I need is true, that would only prove the statement for sufficiently large $n$. We'd still need to check some number of smallish cases by hand. I've already checked at least up through $n=10,000$ though, and it seems fine at least that far.
Good luck getting a full answer! I think it's totally possible that this question may be answerable by some much simpler means. This is just the first approach I thought about.
Best Answer
Bearing in mind that for $ k > n$ or $ k < 0$, ${ n \choose k } =0 $, we can write $a_n = \sum_{k= - \infty } ^\infty { n \choose 3k}$. This allows us to avoid the "have to consider $n \pmod{3}$ cases".
Then use the identity $ { n\choose k } = { n-1 \choose k-1 } + { n - 1 \choose k }$ (which is still true when $k > n$ or $k < 0$) to iteratively reduce $a_n - 3 a_{n-1} + 3a_{n-2} + 2 a_{n-3}$, IE
$= \left[ \sum_{k} { n \choose 3k} \right] - 3 a_{n-1} + 3a_{n-2} - 2 a_{n-3} $
$ = \left[ \sum_{k} { n-1 \choose 3k-1} + {n-1 \choose 3k }\right] - 3 a_{n-1} + 3a_{n-2} - 2 a_{n-3}$
$ = \left[ \sum_{k} { n-1 \choose 3k-1} - 2 {n-1 \choose 3k }\right] + 3a_{n-2} - 2 a_{n-3}$
$ = \ldots $
Can you complete this to show that it equals 0?