The only solution is $f(x) = (-1)^x$.

To prove this, let's first consider the case $n = 1$.
$$f(x) + 2f(1-x) = (-1)^{x+1}.$$
By replacing $x$ with $1-x$, we have
$$f(1-x) + 2f(x) = (-1)^x.$$
Hence, $f(x) = (-1)^x$. Also, we can check this is a solution for $n = 1$.

For general $n$, we can assume the following proposition: The one and only solution of
$$\sum_{k=0}^{2^n-1-1} 2^{r(k)} f(k + (-1)^k x) = (-1)^{x+n-1}$$
is $f(x) = (-1)^x$. Now, we're going to prove it's also true for $n$. Let
$$g(x) = -f(x) - 2f(2^n - 1 - x),$$
then
$$\begin{aligned} 2^{r(k)} g(k + (-1)^k x) &= -2^{r(k)} f(k + (-1)^k x) - 2^{r(k)+1} f(2^n - 1 - k + (-1)^{k+1}x) \\ &= -2^{r(k)} f(k + (-1)^k x) - 2^{r(2^n-1-k)} f(2^n - 1 - k + (-1)^{2^n-1-k}x). \end{aligned}$$
Here we've used the property of $r(k)$, $r(k)+1 = r(2^n-1-k)$ for all $0 \le k \le 2^{n-1}-1$.

Next, by summing over $k$, we can get
$$\sum_{k=0}^{2^n-1-1} 2^{r(k)} g(k + (-1)^k x) = - \sum_{k=0}^{2^n-1} 2^{r(k)} f(k + (-1)^k x) = (-1)^{x+n-1}.$$
Therefore, $g(x) = (-1)^x$, and hence $f(x) = (-1)^x$ can be derived from the way similar to the case $n = 1$. Also, $f(x) = (-1)^x$ satisfies that $-f(x) - 2f(2^n-1-x) = (-1)^x = g(x)$, hence it is a solution.