I can see why $H^*$ is collision resistant for inputs with the same length, but I can't see why the same holds for general inputs whose length is a power of two.

Say $H'$ is a collision-resistant hash function that for a key $hk\in \{0,1\}^n$ maps $\{0,1\}^{2n}$ to $\{0,1\}^{n-1}$.

Then $H_{hk}(x):=\begin{cases} H'_{hk}(x)1&x\neq0^{2n}\\0^n&x=0^{2n}\end{cases}$ should be a collision-resistant hash function that for a key $hk\in \{0,1\}^n$ maps $\{0,1\}^{2n}$ to $\{0,1\}^{n}$, right?

However, $H^*_{hk}(0^{k})=H^*_{hk}(0^{2k})=0^{n}$.