Edit: Okay, I added the details below. I missed this in my original skim of the argument, but the (k=3) is most easily handled as an exception as well. To make (my) life easier, I've slightly altered some of the notation. (For instance, $\log=\ln$)
Original post: Not a full answer, but here’s a sketch (the $k=1$ case is invalid, the $k=2$ case is trivial, and the $k=3$ case is easy):
Show that for every $k\in\mathbb{N}_{\geq 4}$, the function $$f_{k}\left(x\right)\ :=\ \left(1-\tfrac{1}{k}\right)^{x}-\left(1-\tfrac{2}{k}\right)^{x}$$ defined for $x\in\left(-\infty,\infty\right)$ attains a unique local maximum, before which it is strictly increasing, and after which it is strictly decreasing. It follows that on any closed subinterval of $\left[1,\infty\right)$, $f_{k}$ is minimized (only) at (one or both of) the endpoints.
Show that the function $$\alpha_{0}\left(k\right)\ :=\ \underbrace{\left(1-\tfrac{1}{k}\right)^{\log\left(2\right)k}}_{:=\ \alpha_{0;1}\left(k\right)}\ -\ \underbrace{\left(1-\tfrac{2}{k}\right)^{\log\left(2\right)k}}_{:=\ \alpha_{0;2}\left(k\right)}$$ defined for $k\in\left[4,\infty\right)$ is strictly decreasing and attains a limit of $\tfrac{1}{4}$ as $k\to\infty$.
Show that the function $$\alpha_{1}\left(k\right)\ :=\ \underbrace{\left(1-\tfrac{1}{k}\right)^{\log\left(2\right)k-1}}_{:=\ \alpha_{1;1}\left(k\right)}\ -\ \underbrace{\left(1-\tfrac{2}{k}\right)^{\log\left(2\right)k-1}}_{:=\ \alpha_{1;2}\left(k\right)}$$ defined for $k\in\left[4,\infty\right)$ is strictly decreasing and attains a limit of $\tfrac{1}{4}$ as $k\to\infty$.
Conclude that for any $k\in\mathbb{N}_{\geq 4}$,
\begin{align*}
\left(1-\tfrac{1}{k}\right)^{\left\lfloor \log\left(2\right)k\right\rfloor} - \left(1-\tfrac{2}{k}\right)^{\left\lfloor \log\left(2\right)k\right\rfloor}\ &>\ \min\left(\left(1-\tfrac{1}{k}\right)^{\log\left(2\right)k} - \left(1-\tfrac{2}{k}\right)^{\log\left(2\right)k-1},\ \left(1-\tfrac{1}{k}\right)^{\log\left(2\right)k-1} - \left(1-\tfrac{2}{k}\right)^{\log\left(2\right)k-1}\right)\\
&>\ \tfrac{1}{4}
\end{align*}
so that $\left\lfloor \log\left(2\right)k\right\rfloor$ is the desired natural.
Proof of Claim 1: Indeed, for $k>2$ we have that
\begin{align*}
\frac{\text{d}f_{k}}{\text{d}x}\left(x\right)\ >\ 0\ &\iff\ \log\left(1-\tfrac{1}{k}\right)\exp\left(\log\left(1-\tfrac{1}{k}\right)x\right)-\log\left(1-\tfrac{2}{k}\right)\exp\left(\log\left(1-\tfrac{2}{k}\right)x\right)\ >\ 0\\
&\iff\ \log\left(-\log\left(1-\tfrac{2}{k}\right)\right)\ +\ \log\left(1-\tfrac{2}{k}\right)x\ >\ \log\left(-\log\left(1-\tfrac{1}{k}\right)\right)\ +\ \log\left(1-\tfrac{1}{k}\right)x\\
&\iff\ \frac{\log\left(-\log\left(1-\tfrac{2}{k}\right)\right)-\log\left(-\log\left(1-\tfrac{1}{k}\right)\right)}{\log\left(1-\tfrac{1}{k}\right)-\log\left(1-\tfrac{2}{k}\right)}\ >\ x
\end{align*}
and by a symmetric argument that $$\frac{\text{d}f_{k}}{\text{d}x}\left(x\right)\ <\ 0\ \iff\ \frac{\log\left(-\log\left(1-\tfrac{2}{k}\right)\right)-\log\left(-\log\left(1-\tfrac{1}{k}\right)\right)}{\log\left(1-\tfrac{1}{k}\right)-\log\left(1-\tfrac{2}{k}\right)}\ <\ x\text{.}$$ Claim 1 follows. $\Box$
(Be very careful about the signs involved!)
Proof of Claim 2: We need to show that $$\frac{\text{d}\alpha_{1}}{\text{d}k}\left(k\right)\ <\ 0$$ for all (real!) $k\geq 4$. It suffices to show that $$\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right),\ \frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)\ >\ 0\ \text{ and }\ \frac{\frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)}{\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right)}\ >\ 1$$ for such $k$, where we compute that $$\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right)\ =\ \log\left(2\right)\left(\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}}{1-\frac{1}{k}}\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{1}{k}\right)k\right)$$ $$\frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)\ =\ \log\left(2\right)\left(\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}}{1-\frac{2}{k}}\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{2}{k}\right)k\right)\text{.}$$ To this end, we first validate the claim that $\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right)$ and $\frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)$ are (strictly) positive for such $k$. Expanding via the Mercator and geometric series,
\begin{align*}
\frac{\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right)}{\underbrace{\log\left(2\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{1}{k}\right)k\right)}_{>\ 0}}\ &=\ \log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}}{1-\frac{1}{k}}\\
&=\ \sum_{d=1}^{\infty} -\tfrac{d^{-1}}{k^{d}}\ +\ \sum_{d=1}^{\infty} \tfrac{1}{k^{d}}\\
&=\ \sum_{d=1}^{\infty} \tfrac{1-d^{-1}}{k^{d}}\\
&>\ 0
\end{align*}
and likewise
\begin{align*}
\frac{\frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)}{\underbrace{\log\left(2\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{2}{k}\right)k\right)}_{>\ 0}}\ &=\ \log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}}{1-\frac{2}{k}}\\
&=\ \sum_{d=1}^{\infty} -\tfrac{d^{-1}2^{d}}{k^{d}}\ +\ \sum_{d=1}^{\infty} \tfrac{2^{d}}{k^{d}}\\
&=\ \sum_{d=1}^{\infty} \tfrac{\left(1-d^{-1}\right)2^{d}}{k^{d}}\\
&>\ 0
\end{align*}
(where convergence is absolute so causes no issues). Now, $$\frac{\frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)}{\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right)}\ =\ \frac{\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}}{1-\frac{2}{k}}}{\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}}{1-\frac{1}{k}}}\ \exp\left(\log\left(2\right)k\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)\text{.}$$ Let us analyze the two multiplicands separately. First,
\begin{align*}
\frac{\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}}{1-\frac{2}{k}}}{\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}}{1-\frac{1}{k}}}\ &=\ \frac{\sum_{d=1}^{\infty} \tfrac{\left(1-d^{-1}\right)2^{d}}{k^{d}}}{\sum_{d=1}^{\infty} \tfrac{1-d^{-1}}{k^{d}}}\\
&=\ \frac{4+8\sum_{d=3}^{\infty} \tfrac{1-d^{-1}}{k^{d-2}}+\overbrace{\sum_{d=3}^{\infty}\tfrac{\left(1-d^{-1}\right)\left(2^{d}-8\right)}{k^{d-2}}}^{>\ 0}}{1+2\sum_{d=3}^{\infty} \tfrac{1-d^{-1}}{k^{d-2}}}\\
&>\ 4
\end{align*}
(for all $k>2$, so definitely all $k\geq 4$). On the other hand,
\begin{align*}
\frac{\log\left(\exp\left(\log\left(2\right)k\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)\right)}{\log\left(2\right)}\ &=\ k\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\\
&=\ k\left(-\sum_{d=1}^{\infty} \frac{d^{-1}2^{d}}{k^{d}}+\sum_{d=1}^{\infty} \frac{d^{-1}}{k^{d}}\right)\\
&=\ -\sum_{d=1}^{\infty} \frac{d^{-1}\left(2^{d}-1\right)}{k^{d-1}}\text{.}
\end{align*}
As each summand $-\frac{d^{-1}\left(2^{d}-1\right)}{k^{d-1}}$ is strictly increasing in $k$ (again, watch out for the signs), it follows that $$\frac{\log\left(\exp\left(\log\left(2\right)k\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)\right)}{\log\left(2\right)}$$ and thus $$\exp\left(\log\left(2\right)k\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)$$ itself is strictly increasing in $k$. As $$\exp\left(4\log\left(2\right)\left(\log\left(1-\tfrac{2}{4}\right)-\log\left(1-\tfrac{1}{4}\right)\right)\right)\ >\ \tfrac{1}{4}\text{,}$$ for $k\geq 4$, we conclude that
\begin{align*}
\frac{\frac{\text{d}\alpha_{0;2}}{\text{d}k}\left(k\right)}{\frac{\text{d}\alpha_{0;1}}{\text{d}k}\left(k\right)}\ &=\ \underbrace{\frac{\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}}{1-\frac{2}{k}}}{\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}}{1-\frac{1}{k}}}}_{>\ 4}\ \underbrace{\exp\left(\log\left(2\right)k\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)}_{>\ \tfrac{1}{4}}\\
&>\ 1\text{,}
\end{align*}
completing the proof of Claim 2. $\Box$
Proof of Claim 3: We need to show that $$\frac{\text{d}\alpha_{1}}{\text{d}k}\left(k\right)\ <\ 0$$ for all (real!) $k\geq 4$. It suffices to show that $$\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right),\ \frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)\ <\ 0\text{ and }\ \frac{\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)}{\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right)}\ <\ 1$$ for such $k$, where we compute that $$\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right)\ =\ \log\left(2\right)\left(\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}-\tfrac{\log\left(2\right)^{-1}}{k^{2}}}{1-\frac{1}{k}}\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{1}{k}\right)\left(k-\log\left(2\right)^{-1}\right)\right)$$ $$\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)\ =\ \log\left(2\right)\left(\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}-\tfrac{2\log\left(2\right)^{-1}}{k^{2}}}{1-\frac{2}{k}}\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{2}{k}\right)\left(k-\log\left(2\right)^{-1}\right)\right)\text{.}$$ To this end, we first claim that $\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right)$ and $\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)$ are (strictly) negative for such $k$. Expanding,
\begin{align*}
\frac{\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right)}{\underbrace{\log\left(2\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{1}{k}\right)\left(k-\log\left(2\right)^{-1}\right)\right)}_{>\ 0}}\ &=\ \log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}-\tfrac{\log\left(2\right)^{-1}}{k^{2}}}{1-\frac{1}{k}}\\
&=\ \sum_{d=2}^{\infty} \tfrac{\overbrace{-\log\left(2\right)^{-1}+1-d^{-1}}^{<\ 0}}{k^{d}}\\
&<\ 0
\end{align*}
(for all $k>1$, so certainly all $k\geq 4$), and likewise that
\begin{align*}
\frac{\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)}{\underbrace{\log\left(2\right)\exp\left(\log\left(2\right)\log\left(1-\tfrac{2}{k}\right)\left(k-\log\left(2\right)^{-1}\right)\right)}_{>\ 0}}\ &=\ \log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}-\tfrac{2\log\left(2\right)^{-1}}{k^{2}}}{1-\frac{2}{k}}\\
&=\ \sum_{d=2}^{\infty} \tfrac{\left(1-0.5\log\left(2\right)^{-1}-d^{-1}\right)2^{d}}{k^{d}}\\
&=\ \tfrac{\overbrace{-2\log\left(2\right)^{-1}+2}^{<\ 0}}{k^{2}}\ +\ \tfrac{\overbrace{-4\log\left(2\right)^{-1}+\tfrac{16}{3}}^{<\ 0}}{k^{3}}\ +\ \tfrac{1}{k^{4}}\sum_{d=4}^{\infty} \tfrac{\overbrace{\left(16-8\log\left(2\right)^{-1}-16d^{-1}\right)}^{>\ 0}2^{d-4}}{k^{d-4}}\\
&<\ \tfrac{-2\log\left(2\right)^{-1}+2}{\tfrac{k^{4}}{16}}\ +\ \tfrac{-4\log\left(2\right)^{-1}+\tfrac{16}{3}}{\tfrac{k^{4}}{4}}\ +\ \tfrac{1}{k^{4}}\sum_{d=4}^{\infty} \tfrac{\left(16-8\log\left(2\right)^{-1}\right)2^{d-4}}{4^{d-4}}\\
&=\ \tfrac{\overbrace{\tfrac{256}{3}-64\log\left(2\right)^{-1}}^{<\ 0}}{k^{4}}\\
&<\ 0
\end{align*}
for $k\geq 4$, completing the proof of the negativity of $\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)$ for $k\geq 4$. Now, $$\frac{\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)}{\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right)}\ =\ \frac{\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}-\tfrac{2\log\left(2\right)^{-1}}{k^{2}}}{1-\tfrac{2}{k}}}{\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}-\tfrac{\log\left(2\right)^{-1}}{k^{2}}}{1-\tfrac{1}{k}}}\ \exp\left(\log\left(2\right)\left(k-\log\left(2\right)^{-1}\right)\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)\text{.}$$ As before, we analyze the two multiplicands separately. First,
\begin{align*}
\frac{\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}-\tfrac{2\log\left(2\right)^{-1}}{k^{2}}}{1-\tfrac{2}{k}}}{\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}-\tfrac{\log\left(2\right)^{-1}}{k^{2}}}{1-\tfrac{1}{k}}}\ &=\ \frac{\sum_{d=2}^{\infty} \tfrac{\left(1-0.5\log\left(2\right)^{-1}-d^{-1}\right)2^{d}}{k^{d}}}{\sum_{d=2}^{\infty} \tfrac{-\log\left(2\right)^{-1}+1-d^{-1}}{k^{d}}}\\
&=\ \frac{\tfrac{\overbrace{2\log\left(2\right)^{-1}-2}^{>\ 0}}{k^{2}}\ +\ \tfrac{\overbrace{4\log\left(2\right)^{-1}-\tfrac{16}{3}}^{>\ 0}}{k^{3}}\ +\ \tfrac{1}{k^{4}}\sum_{d=4}^{\infty} \tfrac{\overbrace{\left(-16+8\log\left(2\right)^{-1}+16d^{-1}\right)2^{d-4}}^{<\ 0}}{k^{d-4}}}{\tfrac{\overbrace{\log\left(2\right)^{-1}-\tfrac{1}{2}}^{>\ 0}}{k^{2}}\ +\ \sum_{d=3}^{\infty} \tfrac{\overbrace{\log\left(2\right)^{-1}-1+d^{-1}}^{>\ 0}}{k^{d}}}\\
&<\ \frac{\tfrac{2\log\left(2\right)^{-1}-2}{k^{2}}\ +\ \tfrac{4\log\left(2\right)^{-1}-\tfrac{16}{3}}{4k^{2}}}{\tfrac{\log\left(2\right)^{-1}-\tfrac{1}{2}}{k^{2}}}\\
&=\ \frac{3\log\left(2\right)^{-1}-\tfrac{10}{3}}{\log\left(2\right)^{-1}-\tfrac{1}{2}}\\
&<\ 2
\end{align*}
for $k\geq 4$. On the other hand,
\begin{align*}
\frac{\log\left(\exp\left(\log\left(2\right)\left(k-\log\left(2\right)^{-1}\right)\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)\right)}{\log\left(2\right)}\ &=\ -\left(k-\log\left(2\right)^{-1}\right)\sum_{d=1}^{\infty} \frac{d^{-1}\left(2^{d}-1\right)}{k^{d}}\\
&=\ -1\ +\ \sum_{d=1}^{\infty} \frac{\overbrace{-\left(d+1\right)^{-1}\left(2^{d+1}-1\right)\ +\ d^{-1}\left(2^{d}-1\right)\log\left(2\right)^{-1}}^{<\ 0}}{k^{d}}\\
&<\ -1\text{,}
\end{align*}
from which it immediately follows that $$\exp\left(\log\left(2\right)\left(k-\log\left(2\right)^{-1}\right)\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)\ <\ \tfrac{1}{2}\text{.}$$ We conclude that
\begin{align*}
\frac{\frac{\text{d}\alpha_{1;2}}{\text{d}k}\left(k\right)}{\frac{\text{d}\alpha_{1;1}}{\text{d}k}\left(k\right)}\ &=\ \underbrace{\frac{\log\left(1-\tfrac{2}{k}\right)\ +\ \frac{\tfrac{2}{k}-\tfrac{2\log\left(2\right)^{-1}}{k^{2}}}{1-\tfrac{2}{k}}}{\log\left(1-\tfrac{1}{k}\right)\ +\ \frac{\tfrac{1}{k}-\tfrac{\log\left(2\right)^{-1}}{k^{2}}}{1-\tfrac{1}{k}}}}_{<\ 2}\ \underbrace{\exp\left(\log\left(2\right)\left(k-\log\left(2\right)^{-1}\right)\left(\log\left(1-\tfrac{2}{k}\right)-\log\left(1-\tfrac{1}{k}\right)\right)\right)}_{<\ \tfrac{1}{2}}\\
&<\ 1\text{,}
\end{align*}
completing the proof of Claim 3. $\Box$
That covers our bases. Let me know if there are (inevitable) typos, I guess... $\blacksquare$
