First consider the case when $m$ is prime. Choose $\ell$ so that $m^\ell>k$, and consider the number $n=am^\ell+k$ with $a\in\mathbb N$. By Lucas's theorem, we see that $\textstyle\binom{n}{k}$ is $1\pmod{m}$. So taking sufficiently large $n\equiv k\pmod{m^\ell}$ will ensure $\textstyle\binom{n}{k}$ is coprime to $m$. Now if $m$ is a product of several prime powers, we choose such $n$'s for each of the prime factors as in the preceding paragraph, and combine them via CRT, which should work. $\blacksquare$

I think Lucas is even an overkill: I claim that any $n \equiv k \pmod{m \cdot k!}$ will do the job. Indeed, this will imply that \[m \cdot (m-1) \cdots (m-k+1) \equiv k! \pmod{m \cdot k!}\]and hence \[\binom{m}{k} \equiv 1 \pmod{m}.\]