Solving a set of linear recurrences is indeed a good, elementary way to go, but if you solve the recurrences in the answer by @Canardini - which I did using wolfram alpha - you find that the answer is $E_X = 46656 = 6^6$. This is such a special number that you might wonder if there is a more fundamental explanation, and indeed there is, using more powerful theorems of Markov Chains.
Claim: If the desired string $x$ has the property that two copies of $x$ cannot overlap (which holds for $x = 123456$ in the OP question but does not hold for e.g. $x=111111$ or $x=121212$), then the expected time to first occurrence of $x$ is $6^L$ where $L$ is the length of $x$.
Consider a Markov Chain with $6^6$ states, where each state is a possible sequence in $\{1,2,3,4,5,6\}^6$ and records the last $6$ rolls. Each state can transition to $6$ states (i.e. it has "out-degree" $6$) with equal prob $1/6$. E.g. the state $\color{red}{1}13462$ can transition to $13462\color{blue}{j}$ where $\color{blue}{j}$ can be any of $\{1,2,3,4,5,6\}$. The red $\color{red}{1}$ represents the oldest die-roll result that has "aged out" and the blue $\color{blue}{j}$ represents the newest die-roll result. Note that each state also has "in-degree" $6$, i.e. only $6$ states can transition to it. (Self-loops are possible and count as both in-degree and out-degree.)
It is obvious such a Markov Chain is aperiodic, positive recurrent, irreducible, ergodic, etc., all the good stuff. Further, because every state's in-degree $=$ out-degree $= 6$, the chain's unique stationary distribution $\pi$ (also its limiting distribution) is the $6^6$-long vector whose every entry is $6^{-6}$.
A powerful (but somewhat "intuitively obvious?") theorem says that, if $\tau_{xx}$ is the revisit time from state $x$ back to state $x$, then:
Theorem: for a positive recurrent Markov Chain, with stationary distribution $\pi, E[\tau_{xx}] = 1 / \pi_x$ for any state $x$.
E.g. see Prop 2.6 of these notes or Theorem 1.19 of these notes or (for a slightly different version) wikipedia
IMHO this theorem is "intuitively obvious" in the following sense: the limiting distribution $\pi$ means in the long run the chain is going to spend $\pi_x$ fraction of the time in state $x$, so it only makes sense that the inter-visit time $\tau_{xx}$ has an expected value of $1/\pi_x$. However, such an "intuitive" argument is not rigorous, and the theorem has a non-trivial proof making use of positive recurrence.
Anyway, based on this theorem, and letting $x=123456$ the state we're interested in, we have $E[\tau_{xx}] = 1/6^{-6} = 6^6$. I.e., if we have just rolled $123456$, then the expected time to roll the next $123456$ is $6^6$. This isn't the same as the OP question. However, if we have just rolled $123456$, then none of these old roll-results can be part of the next $123456$, and therefore this is equivalent to rolling from the very beginning (when the "history" of rolls is the empty string). This is a direct result of the fact that two strings of $123456$ cannot overlap. So the same expected time $6^6$ also answers the OP question.
Addendum: for some other strings, this theorem also gives a quick way to find expected time of first occurrence. E.g. consider $y=111111$. The same theorem says that $E[\tau_{yy}] = 6^6$. But it is also obvious that revisit can either happen right away (if the next roll is $1$) or much later. I.e.:
$$E[\tau_{yy}] = 1 + (\frac16 \times 0 + \frac56 \times E[T_y])$$
where $T_y=$ time to first occurrence of $y$ starting with no useful history (including the case of starting from scratch, i.e. empty history). Solving for this we have:
$$E[T_y] = (6^6 - 1) \times \frac65 = 55986$$
which can be easily verified by solving the corresponding set of linear recurrences for the string $y=111111$.
If you draw with replacement instead, then this is the coupon collector's problem, which has a simple solution and is still a good approximation of your situation (since drawing the same card twice on a given day is unlikely).
The expected number of draws to get all coupons from a set of $n$ is $n\sum_{k=1}^n\frac1k\approx n \log n + \gamma n + \frac12$, where $\gamma$ is Euler's constant. For $n=600$, this is about $4185$ draws, or $2092.5$ days at two draws/day.
We can adjust this to simulate drawing without replacement on each day. Drawing two cards without replacement is equivalent to drawing with replacement until we've seen two different cards. If we do this, each draw after the first one has an $\frac{n-1}n$ chance of being different from the first, so the expected number of draws per day is $1+\frac n{n-1}=2+\frac1{n-1}$. At this rate, it takes about $4185/(2+\frac1{599})\approx2090.75$ days to see all the cards.
Best Answer
The digits of 2^n are pseudo-random (hard to predict, behaving like random except they are of course deterministic) except for the first and last few digits. So if you calculate values 2^n until you produced 10,000 digits, there is a good chance that four consecutive digits equal 2018, or any other four digit sequence. Of course it may happen a bit earlier or later.
2^n has roughly 0.3n digits. The powers 2^k for k <= n have a total of 0.15n^2 digits. You can reasonably expect a solution for some k <= sqrt(10,000 / 0.15) or k <= 260, which would have about 78 digits.
A much smaller solution (say k <= 100) or having to calculate many more powers (say first k >= 1000) is possible, but unlikely.
And as said elsewhere, there is an infinite number of k such that 2^k even starts with 2018.