No it's not true. An equivalent question is whether the product of $(1-1/p)$, where $p$ ranges over all the primes for which 2 has odd order mod $p$, is greater than or equal to $1/2$. However an explicit calculation shows that if you take the product over all primes $p$ less than 57 million with this property then the product is just less than $1/2$, so there will be a counterexample; however $k$ will be astronomical (the lowest common multiple of these millions of orders, many of which will be a million or more).

No it's not true. An equivalent question is whether the product of $(1-1/p)$, where $p$ ranges over all the primes for which 2 has odd order mod $p$, is greater than or equal to $1/2$. However an explicit calculation shows that if you take the product over all primes $p$ less than 57 million with this property then the product is just less than $1/2$, so there will be a counterexample; however $k$ will be astronomical (the lowest common multiple of these millions of orders, many of which will be a million or more). Computing the product instead of the lowest common multiple gives some value of $k$ which has 6482632 digits (the product becomes less than $1/2$ when $p=55685687$), but the smallest counterexample will be smaller than that because the LCM will save you something (although it will still be astronomical).