Here is the full proof based on ArturoMagidin's comments on the original post (this proof appears in a book that I am writing and a paper that I wrote that is currently under review). Let $k\ge 2$ and $n\ge 3$ be fixed integers. As I wrote in the proof here, the invertible elements modulo $2^n$ are given by the $\varphi(2^n) = 2^{n-1}$ distinct elements of $$S=\left\{\pm 5^k : k\in [2^{n-2}]\right\},$$ where $[t]$ denotes $\{1,2,\ldots, t\}$. We will show that
$$|S_k (2^n)| =
\begin{cases}
\hfill \dfrac{2^{n-2}}{(k, 2^{n-2})} &\text{ if } 2\mid k\\
\hfill 2^{n-1} &\text{ if } 2\nmid k
\end{cases}.
$$
where $S_k (n)$ denotes the set of reduced $k^{\text{th}}$ power residue classes modulo $n$, meaning those residue classes that are coprime to $n$.
We will use the fact that, for $k\ge 2$, the $k^{\text{th}}$ power map modulo an integer $n\ge 2$ is bijective on the set of reduced residue classes modulo $n$ if and only if $(k,\varphi(n))=1.$ Let $k=2^j m,$ where $m$ is odd. If $j=0,$ then the exponent $k$ is odd and so coprime to $2^n.$ By the aforementioned fact, all integers coprime to $2^n$ are in $S_k (2^n),$ so $|S_k (n)| = 2^{n-1}.$ Now we can assume that $j\ge 1.$ We can think of the $k^{\text{th}}$ power map as taking a power of $m$ of each element of $S$ followed by taking a power of $2^j$ of each element of $S.$ Again by the aforementioned fact, the first map is irrelevant because it is a bijection on $S.$ What really matters is the application of the second map to $$S=\left\{\pm 5^k : k\in [2^{n-2}]\right\}.$$ Since $j\ge 1,$ we can remove any negative signs and we get the set $$T=\left\{ (5^k)^{2^j} : k\in [2^{n-2}]\right\}.$$ Not every $(5^k)^{2^j}$ is necessarily distinct modulo $2^n$ so we have to determine to amount of duplication, or rather the number of distinct elements defined as that will be the cardinality of $S_k (2^n)$. We rewrite each element as $(5^{2^j})^k$ for $1\le k\le 2^{n-2}.$ By the standard proof of the fact that there is no primitive root modulo powers of $2$ (which proves that odd integers have order less than or equal to $2^{n-2}$ modulo $2^n$), we find that $$(5^{2^j})^{2^{n-2}} \equiv (5^{2^{n-2}})^{2^j}\equiv 1^{2^j} \equiv 1\pmod{2^n},$$ and higher powers of $5^{2^j}$ cycle through lower powers. So all elements generated by the powers of $5^{2^j}$ are in $T,$ in addition to every element of $T$ being a power of $5^{2^j}.$ Thus, the number of distinct elements of $T$ modulo $2^n,$ and therefore the cardinality of $S_k (2^n),$ is $$|S_k (2^n)| =\text{ord}_{2^n}(5^{2^j})=\frac{\text{ord}_{2^n}(5)}{(2^j, \text{ord}_{2^n}(5))}=\frac{2^{n-2}}{(2^j, 2^{n-2})}=\frac{2^{n-2}}{(k, 2^{n-2})}.$$
