This can be done in an elementary way using the Chinese remainder theorem.
First of all, note $m$ only appears in the conclusion in the context of the product
$mn$. For any common prime factor of $m$ and $n$ suck that prime's contribution to $m$ into $n$ instead, which changes the meaning of $m$ and $n$ but does not alter $mn$ nor alter the meaning of $r$ being coprime to $n$. It does change the meaning of what a congruence mod $n$ is, but only by making the condition even stronger.
Thus we are reduced to the case that $m$ and $n$ are relatively prime, so
now solve $r' \equiv r \bmod n$ and $r' \equiv 1 \bmod m$.
[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}$.
Best Answer
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.