I found it interesting to consider the problem with the minus rather than plus sign in front of the sum:
$$(\star)\qquad 3^n s - \sum_{k=0}^{n-1} 3^{n-1-k} a^{a_k} = 2^m.$$

Consider the function 
$$f(x):=3x-2^{\lfloor \log_2(3x)\rfloor}.$$

It can be easily seen that iterations of $f(x)$ have 1-cycles at powers of $2$, and 1--cycles of the form $(5\cdot 2^t,7\cdot 2^t)$. I conjecture that there exists no other cycles. Under this conjecture, the question on representation $(\star)$ has an easy answer.

First, assume that iterations of $f$ starting at $x=s$ end at a power of $2$. Let $2^m$ denote this power, $n$ denote the number of iterations to reach $2^m$, and $s_0:=s\to s_1\to s_2\to \dots \to s_n:=2^m$ be the sequence of iterated values of $f$.
Then
$$3^n s - \sum_{k=0}^{n-1} 3^{n-1-k} (3s_k - s_{k+1}) = 2^m$$
has the form $(\star)$ since $3s_k - s_{k+1}$ are powers of $2$.

For example, for $s=456$, iterations of $f$ give $456\to 344\to 8$ gives the following identity:
$$3^2 456-3\cdot 2^{10} - 2^{10} = 2^3.$$

Second, if the iterations of $f$ lead to the cycle $(5\cdot 2^t,7\cdot 2^t)$, we artificially replace it with $5\cdot 2^t\to 11\cdot 2^t\to 2^t$, and proceed as above.

For example, for $s=120$, iterations of $f$ give $120\to 104\to 56\to 40\to 56\to\dots$. We replace it with $120\to 104\to 56\to 40\to 88\to 8$, which corresponds to the identity:
$$3^5 120 - 3^4 2^8 - 3^3 2^8 -3^2 2^7 - 3\cdot 2^5 - 2^8 = 2^3.$$