For $ k\le10000$ the problem is trivial, since $ k$ itself does the job. For $ k > 10000$, we have an $ n < k$ such that $ 10^{n}< k^{4}< 16^{n}$ (and thus $ 2^{n}> k$). For this $ n$, consider \[ S=\{k\in\mathbb{N}|10^{n}\le k<10^{n+1}\text{ and }k\text{ only consists of digits }0\text{ and }1\text{.}\},\] then $ |S| = 2^{n}> k$ and therefor contains two elements $ s_{1}> s_{2}$ with same remainder modulo $ k$. So, $ k|s_{1}-s_{2}$, and $ s_{1}-s_{2}< 10^{n}< k^{4}$. On the other hand, differences of two numbers in $ S$ have only digits $ 0,1,8,9$, so we're done.