[Edited again mostly to spell out why the $m_j \bmod a$ are distinct.]
Yes, the desired result is true for all $k$. The following proof
is elementary but possibly more algebraic than expected (apparently
some kind of variant of the "polynomial method" in combinatorics, though
with no need for anything as advanced as the "combinatorial Nullstellensatz").
This would make for a good Putnam B-6 problem; indeed I wouldn't be surprised
if this question has already been used for such a competition.
Let $a_1,\ldots,a_k$ be pairwise coprime positive integers,
and set $a = \prod_{i=1}^k a_i$.
For each $i$ let $A_i$ be a nonempty subset of ${\bf Z} / a_i {\bf Z}$,
and let $Z_i$ be the complement of $A_i$ in ${\bf Z} / a_i {\bf Z}$.
Let $A \subseteq {\bf Z} / a {\bf Z}$ consist of the residues $n \bmod a$
such that $n \bmod a_i \in A_i$ for each $i$.
Let $Z$ be the complement of $A$ in ${\bf Z} / a {\bf Z}$, consisting of
the residues $n \bmod a$ such that $n \bmod a_i \in Z_i$ for some $i$.
We claim:
Proposition. This set $Z$ cannot contain a run of
$$
N := \prod_{i=1}^k (a_i - |A_i| + 1) = \prod_{i=1}^k (|Z_i| + 1)
$$
consecutive residues $\bmod a$.
Proof: Let $w \in {\bf C}$ be a primitive root of unity of order $a$,
so that $w_i := w^{a/a_i}$ is a primitive root of unity of order $a_i$
for each $i$.
Set $W_i := \lbrace w_i^n | n \in Z \rbrace$, a set of size $|Z_i|$, and
$P_i(X) := \prod_{x \in W_i} (X-x)$, which is thus a polynomial
of degree $|Z_i|$. Then for any $n \bmod a$ we have $n \in Z$ iff
$$
0 = \prod_{i=1}^k P_i(w_i^n) = P(w^n),
$$
where $P$ is the polynomial defined by
$$
P(X) := \prod_{i=1}^k P_i(X^{a/a_i}).
$$
Because each $P_i(X^{a/a_i})$ is the sum of at most $|Z_i|+1$ monomials,
their product $P$ is the sum of at most $\prod_{i=1}^k (|Z_i|+1) = N$
monomials, say
$$
P(X) = \sum_{j=1}^N c_j X^{m_j}.
$$
The $N$ exponents $m_j$ are the integers of the form $a \sum_{i=1}^k b_i/a_i$
with $0 \leq b_i \leq |Z_i|$. Since each $|Z_i| < a_i$ (this is where
we use the hypothesis $A_i \neq \emptyset$) and the $a_i$ are pairwise
coprime, it follows that these $m_j$ have pairwise distinct residues
$\bmod a$.
We claim, then, that for each $n \bmod a$ at least one of
$P(w^n), P(w^{n+1}), \ldots, P(w^{n+N-1})$ is nonzero.
Suppose not. Then $(c_1,\ldots,c_N)$ would be a nonzero solution of
the $N \times N$ linear system
$$
\sum_{j=1}^N w^{m_j (n+k)} c_j = 0 \phantom{\infty} (k=0,1,\ldots,N-1).
$$
Hence $(w^{-nm_1^{\phantom.}} c_1^{\phantom.}, \ldots, w^{-nm_N^{\phantom.}} c_N^{\phantom.})$
would be a nonzero vector
in the kernel of the Vandermonde matrix with entries $(w^{m_j})^k$.
But then some two $w^{m_j}$ would coincide, contradicting our observation
that the residues $m_j \bmod a$ are distinct. This completes the proof.
P.S. Note that we do not even need the formula for
the determinant of a Vandermonde matrix, only
the fact that it is invertible, which can be obtained by interpreting the
kernel of the transposed matrix as the space of polynomials of degree
less than $N$ that vanish at the $N$ distinct points $w^{m_j}$.
For each $n$, the differences $a_{n+1}-a_n$, $a_{n+2}-a_{n+1}$, and $a_{n+2}-a_n$ can only be divisible by powers of $2$ and primes less than or equal to $c$. Since
$$
\frac{a_{n+2}-a_{n+1}}{a_{n+2}-a_n}+\frac{a_{n+1}-a_n}{a_{n+2}-a_n}=1,
$$
this is a solution to the S-unit equation, where $S=\{2\}\cup\{p:p\leq c\}$. This means the sequence $x_n:=(a_{n+1}-a_n)/(a_{n+2}-a_n)$ can only take on finitely many values as $n$ varies.
Let $p$, $p'>c$ be distinct primes each not dividing the numerator of any of the finitely many distinct non-zero values of $x_n - x_{n'}$. Then the sequence $x_n$ has period dividing $p$ and $p'$, hence is constant. Say $x_n=k$ for all $n$. This implies $$a_{n+2}-a_{n+1}=\frac{1-k}{k}(a_{n+1}-a_n),$$
i.e. the differences $a_{n+1}-a_n$ form a geometric progression. Hence either $a_n$ is an arithmetic progression (if the common ratio $(1-k)/k$ is $1$), or $a_n$ has the form
$$
a_n = bc^n+d,
$$
with $b$, $c$, $d\in\mathbb{Z}$. The latter case cannot happen, as Fermat's Little Theorem would imply $a_{n+p-1}\equiv a_n\mod p$ for $p$ sufficiently large.
Best Answer
I'm not sure about the state of art, but here is a rough estimate in terms of $c$ and $\ell:=a_c-a_1$ in the case $c\ll \ell$.
First, we notice that for an integer $M$ satisfying $$M\# ~>~ \big(\frac{c}{2(c-1)}\ell\big)^{c(c-1)/2} ~\geq~ \prod_{1\leq i<j\leq c} (a_j-a_i),$$ where the second inequality follows from AM-GM, there exists a prime $m\leq M$ that does not divide the r.h.s.
Second, taking $M$ as smallest as possible and estimating primorial $M\#$ as $e^M$, we have $$m\leq M\approx \frac{c}2 + \frac{c^2}2\log\frac{\ell}2.$$ I believe this rough estimate can be made rigorous if needed.