I would post this as a comment if I could, because it seems too simple for an answer. You already said that you can find the highest bit with a single instruction (if the number fits into a register). For every result $r$ you get (that is, your number is between $2^r$ and $2^{r+1}-1$), there are only two possible numbers $k$ and $k+1$ of decimal digits. So you could just use $r$ as an index into a lookup table that stores both $k$ and $10^k$, and output $k$ if your number is less than $10^k$, or $k+1$ otherwise.
This can be tested efficiently due to a theorem of Shallit, which builds on a classical result on combinatorics on words:
Every prime has one of 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, and 66600049 (Sloane's A071062) as a subsequence of its decimal digits.
To implement efficiently, I would suggest making an array of permissible 3-digit sequences and reducing mod 1000 (perhaps repeatedly, if testing shows it to be efficient). If you get a hit, you can short-circuit and return "true". Otherwise, convert the number to a string and use a standard regular expression library to efficiently test if
[2357]|1.*[19]|(?:8.*8|9.*(?:0.*0|9)|[46]).*1|(?:4.*[049]|(?:6.*4|9.*4(?:.*6){2}).*6|(?:9.*[069]|6.*(?:(?:0.*0|6.*[06])(?:.*0){3}|(?:6.*6|0).*6|9)).*4|8).*9
matches your number. This should take time linear in the length of the input number, both for conversion (if using an efficient algorithm) and regex testing (if using an efficient algorithm with regex preprocessing).
If you check the whole number in 1000-digit increments you can leave off the testing of the one-digit numbers.
Best Answer
It is known that there is a positive number $\delta$ strictly less than 1 such that, if $n$ is large enough, then there's a prime between $n$ and $n+n^{\delta}$. [I think the state of the art has $\delta=.535$] If $n$ is large enough, then $n$ and $n+n^{\delta}$ start with the same however-many-digits-you-like. So that proves it's always possible, although it doesn't give you a good way to do it.
It is conjectured that there's always a prime between $n$ and $n+C(\log n)^2$ for some positive constant $C$ [$C=2$ may even do, at least for large $n$], but this is way beyong what anyone currently knows how to prove.