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.$$

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} 2^{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 2-cycles of the form $(5\cdot 2^t,7\cdot 2^t)$. I conjecture that there exist 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.$$