Can you post your solution pls?

I will give it a few days first for others to try

Hint for my bound, maybe can be done much better

By considering the last 3 blocks of 4 digits, by pigeonhole I was able to get that there must exist at least 9875 different blocks. However the code I did says that there must exist all 10000. Is it possible to strengthen the bound just by pigeonhole or do you need to go after each block on its own?

Well, I didn't use Pigeonhole

Finally, I think I got it! The proof depends on the following lemma: x is a residue of 2^n (for n >= a), modulo 10^a if x is divisible by 2^a and x isn’t divisible by 5. Proof: notice that order2(5)=4, combining this with LTE we get order2(5^x) = 4*5^(x-1). Hence the cycle of different mods 10^a is of length 4*5^(a-1). Notice that every mod must be divisible by 2^a (well known fact). And no mod can be divisible by 5. Hence there are at most (10^a/(2^a)) * (4/5) = 4*5^(a-1) mod that can occur and since the shortest cycle is of length 4*5^(a-1) - every must occur. Now we prove that every block of 4 numbers occur. Say our block is X. and let 100*X + 10a + b such a number that it’s divisible by 64 (a and b are digits). If b isn’t 0, then by our Lemma, this number occurs as a residue mod 10^6, hence we would be done. If b is 0, then consider the number 10*X + a. It’s divisible by 32, so by our Lemma if a isn’t 0, it occurs as a mod 10^5. Now if a is 0, then going back a little we get that 100*X is divisible by 64, but then so is 100*X + 64, which occurs as a residue. Now we only need to prove that every since mod 10^6 actually occurs. And it’s not hard, since by the Lemma, the cycle is of length 4*5^(5) = 12500 < 20000. We only need to account to the first few cases where 2^n is less than 10^6 (because for example 2048 doesn’t give us 0020), so if we start the cycle from 2^20 > 10^6, after 12500 moves we should get all the blocks, hence giving a bound of n<12521.

$\textbf{Solution.}$ We claim that every multiple of $64$ that do not end with $0$ will appear in exactly one of the powers of $2$ from $2^{6}$ to $2^{4\cdot 5^5+5}$, with leading zeros in the $6$ digits if it is not a non-zero digit. To acheive this step, we will prove that the last $6$ digits among these powers of $2$ must all be distinct. Then since the last $6$ digits in these powers of $2$ must be a multiple of $64$, and there are exactly $4\cdot 5^5$ multiples of $64$ with at most $6$ digits, then every multiple of $64$ will appear exactly once among the powers of $2$. Suppose not, then there exist $6\le x < y\le 4\cdot 5^{5}+5$ such that $2^x\equiv 2^y \pmod {10^6} \iff 10^{6}\mid 2^{x}(2^{y-x}-1)$. Since $x\ge 6$, then the condition holds iff $5^6\mid 2^{x-6}(2^{y-x}-1) \iff 5^6\mid 2^{y-x}-1$. Now we will show that if $p$ is the minimal index such that $5^q\mid 2^p-1$, then $p=\phi(5^q)=4\cdot 5^{q-1}$, then for $q=6$ it will lead to a contradiction that $4\cdot 5^5\le x-y$. First we prove a result that $$(1+3\cdot 5)^{5^{n-2}} \equiv 1+3\cdot 5^{n-1} \pmod {5^n}$$This can be done by induction on $n$. For $n=1$ the result is of course true. For inductive step just note that if $(1+3\cdot 5)^{5^{m-2}} \equiv 1+3\cdot 5^{m-1} \pmod {5^m}$, then for some $\ell \in \{0,1,2,3,4 \} $ we will have $$ (1+3\cdot 5)^{5^{m-1}}\equiv (1+3\cdot 5^{m-1}+ 5^m\ell)^5 \equiv (1+3\cdot 5^{m-1})^5+5(1+3\cdot 5^{m-1})^4\cdot (5^m\ell)$$$$\equiv (1+3\cdot 5^{m-1})^5\equiv 1+5(3\cdot 5^{m-1})= 1+3\cdot 5^m \pmod {5^{m+1}}$$Back to our main claim, observe that if $5\mid 2^p-1$, then $4\mid p$, which proves the base case. Now observe that $2^{4\cdot 5^{q-2}}-1\equiv (1+3\cdot 5)^{5^{q-2}} \equiv 1+3\cdot 5^{q-1} \neq 1 \pmod {5^{q-1}}$, so the minimal index $p$ is is not a divisor $4\cdot 5^{q-2}$. However, it is clear that $p$ is a multiple of $4$ and a divisor of $\phi(5^q)=4\cdot 5^{q-1}$, which means that $p$ must be equal to $4\cdot 5^{q-1}$, as we want to prove. With this result, we have shown that every multiple of $64$ will appear exactly once among $2^{17},2^{18},\cdots 2^{4\cdot 5^5+16}$, with no missing zeroes since $2^{17}>100000$. Now for any four digit number $k=\overline{abcd}$, since $64<100$, we may find a two digit number $w=\overline{uv}$ such that $100k+w=\overline{abcduv}$ is a multiple of $64$, which is in the last $6$ digits of one of the powers of $2$ above. Thus, this power of $2$ say $2^n$, will contain the substring $k$ when written in base $10$, and $n< 4\cdot 5^5+17=12517<20000$ as desired. $\blacksquare$ $\textbf{Comment.}$ The method of proving the main result that $2$ is a primitive root modulo $5^k$ for every $k$, can be used the same way to prove that the following result: If $g$ is a primitive root modulo $p$, and $g^{p-1}\neq 1 \pmod {p^2}$, then $g$ is a primitive root modulo $p^k$ for every $k$.