Power-reduction formula

According to the Power-reduction formula, one can interchange between $\cos(x)^n$ and $\cos(nx)$ like the following: $$ \cos^n\theta = \frac{2}{2^n} \sum_{k=0}^{\frac{n-1}{2}} \binom{n}{k} \cos{((n-2k)\theta)} \tag{odd}\\ $$ $$ \cos^n\theta = \frac{1}{2^n} \binom{n}{\frac{n}{2}} + \frac{2}{2^n} \sum_{k=0}^{\frac{n}{2}-1} \binom{n}{k} \cos{((n-2k)\theta)} \tag{even} $$ To me this looks like an Binomial transform. Is this true?

May I think of it as a change of basis of a vector space?

Yes, it's a binomial expansion:

$$ \begin{eqnarray} \cos^n\theta &=& 2^{-n}\left(\mathrm e^{\mathrm i\theta}+\mathrm e^{-\mathrm i\theta}\right)^n \\ &=& 2^{-n}\sum_{k=0}^n\binom nk\mathrm e^{\mathrm ik\theta}\mathrm e^{-\mathrm i(n-k)\theta} \\ &=& 2^{-n}\sum_{k=0}^n\binom nk\mathrm e^{\mathrm i(2k-n)\theta}\;, \end{eqnarray} $$

and then combining the terms whose exponents differ only by a sign (and whose coefficients coincide) yields the formulas you give. And yes, you may think of it as a change of basis if you wish, since both $\cos^n\theta$ and $\cos n\theta$ are linearly independent sets of functions; this is known from Fourier theory for $\cos n\theta$, and your transformation, which is clearly invertible, shows that it's also true for $\cos^n\theta$.

I don't know about the binomial transform, but you can get it from the binomial theorem after writing $\cos \theta = (e^{i\theta} + e^{-i\theta})/2$.

Yes, in the vector space of functions spanned by $\cos^j (\theta)$ for nonnegative integers $j$ it tells you how to transform to the basis $\cos(j \theta)$.

You can generalize your formulae for odd and even values of $n$. $$ \cos^n\theta = 2^{-n} \sum_{k=0}^n \bigl( \begin{smallmatrix} n \\ k \end{smallmatrix} \bigr) \cos (2k-n)\theta.$$ That looks nice and compact, but if you want to identify the individual cosines you'll need to add $\bigl( \begin{smallmatrix} n \\ k \end{smallmatrix} \bigr) \cos (-\alpha) + \bigl( \begin{smallmatrix} n \\ n-k \end{smallmatrix} \bigr) \cos \alpha = 2\bigl( \begin{smallmatrix} n \\ k \end{smallmatrix} \bigr) \cos \alpha $.