Choose $n$ such that $2^{n-1}\le k < 2^n$. Let $S$ be the set of non-negative integers less than $10^n$ that can be written with digits 0 or 1 only. Clearly, $S$ has $2^n$ elements. By the pigeonhole principle, there must be at least two elements $a$ and $b$ such that $a\equiv b\pmod{k}$. Then we find $\mid a-b\mid$ must be a multiple of $k$.

By studying the possible cases of subtracting a $0$, $1$ digit by another $0$, $1$ digit with possible carries, we can conclude $\min a- b\mid$ can be expressed with digits 0, 1, 8, 9 only.

Meanwhile, $\mid a-b\mid < \underbrace{11\cdots 1}_{n-1} < 10^{n-1} \times 1.2 < 16^{n-1} \le k^4$.