Answer: B

Small Hint:

The number of digits of $2^k$ increases by $1$ exactly when its leading digit forces a carry

Big Hint:

A power of $2$ has leading digit $8$ or $9$ precisely when the previous power has leading digit $4$

Solution:

The smallest power of $2$ with any given digit-count lies between $10^k$ and $2\cdot10^k,$ so it has leading digit $1.$ Because $2^{2004}$ is a $604$-digit number beginning with $1,$ it is the first $604$-digit power. Thus the powers in $S$ contain exactly one leading-$1$ number for each digit-count from $1$ through $603,$ or $603$ in all.

After each leading-$1$ power, the next power leads with $2$ or $3,$ and the following power leads with $4, 5, 6,$ or $7.$ Hence $603$ elements lead with $2$ or $3,$ another $603$ lead with $4$ through $7,$ and the remaining $2004 - 3(603) = 195$ lead with $8$ or $9.$

Finally, halving a power that leads with $8$ or $9$ produces the preceding power with leading digit $4,$ and doubling any leading-$4$ power reverses this. This is a bijection, so there are $195$ elements with first digit $4.$

Thus, the correct answer is B.