Prove $\sum_{k=0}^n\binom{n}{k}\cos\left(\frac{k\pi}{2} - \frac{n\pi}{4}\right) = \sqrt{2^n}$

You first idea is correct.

$$\begin{align} \sum_{k=0}^n\binom nk\cos\left(\frac{k\pi}2-\frac{n\pi}4\right)&= \sum_{k=0}^n\binom nk \Re\left(\exp\left(\frac{k\pi i}2-\frac{n\pi i}4\right)\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)\sum_{k=0}^n\binom nk \left(e^{\pi i/2}\right)^k\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)\sum_{k=0}^n\binom nk i^k\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)(1+i)^n\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)\left(\sqrt2e^{\pi i/4}\right)^n\right)\\ &=\sqrt{2^n} \end{align}$$

This answer adapted from the AoPS link in comments $$\sum_{k=0}^n\binom nk\cos(k\pi/2-n\pi/4)$$ $$=\operatorname{Re}\left(\sum_{k=0}^n\binom nk(\cos(k\pi/2-n\pi/4)+i\sin(k\pi/2-n\pi/4))\right)$$ $$=\operatorname{Re}\left(\sum_{k=0}^n\binom nke^{i(k\pi/2-n\pi/4)}\right)$$ $$=\operatorname{Re}\left(e^{-in\pi/4}\sum_{k=0}^n\binom nk i^k\right)$$ $$=\operatorname{Re}\left(\left(\frac{\sqrt2}2(1+i)\right)^{-n}(1+i)^n\right)$$ $$=\left(\frac{\sqrt2}2\right)^{-n}=2^{n/2}$$