This is more of a comment than an answer, since I want to engage only with some of the issues you mention at the very beginning of your post. I believe that you need to take more care in formulating the Equations Problem.
Specifically, I claim that with your way of describing the equations problem, every infinite group has an enumeration for which the EP is not decidable. So this property can depend on the enumeration, even when the group has another presentation with a decidable word problem. This is because we may find an enumeration $g_0,g_1,g_2,\ldots$ of the elements of the group for which the group operation $g_ig_j=g_k$ is not decidable (equivalently, the function $(i,j)\mapsto k$ is not computable). To find such an enumeration, we simply diagonalize against the possible programs that might compute the group operation: any given finite partial enumeration can be extended so as to disagree with the next program offered as a candidate for computing the operation. And if we have enumerated the group in such a way that the group operation is not computable, then we cannot decide the corresponding EP, since we cannot decide whether $x^{-1}x g_ig_j=g_k$ has a solution or not.
This suggests that you probably want to insist on having a computable presentation of your group, in the sense of computable model theory. So you should only consider enumerations where the group operation is computable. It follows that the inverse operation is also computable, since for any element we can search for the element that multiplies with it to the identify (a fixed parameter of the algorithm).
I spent some time working this problem and discovered the following generalization. There's no new information here about the $2^{x-1}+5$ problem, so this is not much of an answer to that specifically. But we can say some similar things about some similar functions.
Let $F(x)$ be a composition of functions $x$, $c$, $c^\square$, $\square + \square$, $\square \cdot \square$, and $\square!$. For example, we might have $F(x) = 2^{6^x + x^2} + (x !)^2 + 3^x \cdot x - 3$, but not $F(x) = x^x$. Let $F^k(x)$ denote the $k^\text{th}$ iterate of $F$, so for example $F^2(x) = F(F(x))$.
Lemma: $F^k(x) ~\text{mod}~ m$ is eventually periodic in $k$.
Proof: First re-write $F(x)$ so that all the bases are factored into primes, for example $F(x) = 2^{6^x} = 2^{2^x \cdot 3^x}$. Now with $m = p^a \cdot b$ and $(p,b) = 1$, define $g_p(m) = \text{ord}_b(p)$, and observe that $p^{a+x} \equiv p^{(a + x) ~\text{mod}~ g_p(m)} ~\text{mod}~ m$. Assume as an inductive hypothesis that $F^k(x) ~\text{mod}~ n$ is eventually periodic in $k$ for all $1 \leq n < m$. By taking all the exponents $\text{mod}$ an appropriate composition of $g$ functions we get a function $G$ such that for sufficiently large $x$, $F(x) \equiv G(x) ~\text{mod}~ m$ — for example, if $F(x) = 2^{3^x+x}+x^7$, consider $G(x) = 2^{3^{x ~\text{mod}~ g_3(g_2(m))} + x ~\text{mod}~ g_2(m)} + x^7$ — then for sufficiently large $k$ we have $F^{k+1}(x) \equiv G(F^k(x)) ~\text{mod}~ m$ and combined with the inductive hypothesis and $g_p(m) < m$ this implies $F^k(x) ~\text{mod}~ m$ is an eventually periodic function of $k$.
Factorials are allowed too since they are eventually equal to $0 ~\text{mod}~ m$ and we can remove them from the expression, but I'm not sure how to handle general $\square^\square$ power compositions or primorials.
$\square$
Corollary: If $x$ never occurs outside of an exponent in the expression defining $F(x)$, like $F(x) = 2^{x-1} + 5$ and $F(x) = 2^{7^x+x}\cdot 5^x +3$, but not like $F(x) = 2^x + x$ or $F(x) = 2^x \cdot x$, call it restricted. Then $F^k(x) ~\text{mod}~ m$ is eventually fixed (periodic with period $1$) for all $m$ if and only if $F$ is restricted. However, this doesn't really explain why it should be that $F^k(x) ~\vert~ F^{k+1}(x)$ as requested. It's simply a generalization of the observations in Update #1, but it applies to a much wider class of functions than I originally suspected.
Corollary: For all $x, m \in \mathbb{N}$, there exists a $q \in \mathbb{Q}$ such that for all $k \in \mathbb{N}$, $F^k(x) \equiv \lfloor q \cdot m^k \rfloor ~\text{mod}~ m$. If $F$ is restricted then $q$ has a denominator of the form $m^z \cdot (m-1)$.
An idea I have is to compute some of these rationals for various $F, m, x$ and find cases with the same $m$ and two different functions $F$ and $G$ where the corresponding rationals have some of the same base-$m$ digits at the same positions. Since it is impossible to evaluate iterates of $F$ and $G$ beyond small arguments, if there is no obvious reason for this relationship, then determining for exactly which $k$ is it the case that $m ~\vert~ F^k(x) - G^k(y)$ may turn out to be a good puzzle problem requiring essentially the argument above plus calculations.
Best Answer
We can prove that $\log N_k \sim k \log k$ as follows:
If we want to combine a set of $k$ numbers using the four arithmetic operations, we can think of inputting the numbers (in any order) along with the operations into an RPN calculator. There are $k!$ ways of ordering the numbers, $C_{k-1} = \frac1{k}{2k-2 \choose k-1}$ ways of choosing places to insert the arithmetic operations (without running out of numbers on the stack) and $4^{k-1}$ ways of choosing which of the four operations we will insert at each place, for a grand total of $4^{k-1}\frac{(2k-2)!}{(k-1)!}$ ways of combining $k$ numbers with the four operations. If we are given $k$ numbers and we can work with any subset of them (as in the original formulation of $N_k$), then there are $$ \sum_{i=1}^k {k \choose i} 4^{i-1}\frac{(2i-2)!}{(i-1)!} = \sum_{i=1}^k 4^{i-1} C_{i-1} \frac{k!}{(k-i)!} \le 16^k k! \le (16k)^k $$ ways of choosing a subset and then arranging and combining the elements of the subset with the arithmetic operations. Hence $\log N_k \le k(\log k + \log 16)$.
The lower bound is a little bit more interesting. Just by using addition and multiplication, we can prove that $N_{b+r-2} \ge b^r - 1$: We take as our $b + r - 2$ numbers $2, 3, \ldots b-1, 1, b, \ldots b^{r-1}$ (of course we are assuming that $b \ge 2$). Then we can write any positive integer $n < b^r$ as $\sum_{i=0}^{r-1} a_i b^i$, with $0 \le a_i \le b-1$, and then, by collecting the terms with a given "digit" $a_i$, we can write $n$ as a sum of terms of the form $a(b^{i_{a1}} + \ldots + b^{i_{aj_a}})$, where each $a$, $0 \le a \le b-1$, appears at most once. Of course, we can throw out the term with $a=0$, and not write the 1 when $a=1$, so we can write our number with $2, 3, \ldots, b-1, 1, b, \ldots, b^{r-1}$.
If we allow subtraction as well we can use Francois's idea (and the same set of numbers) to show that $N_{b+r-2} \ge ((2b - 1) ^ r - 1)/2$ when $b \ge 2, r \ge 1$.
Even with only addition and multiplication, we obtain (roughly) $N_k \ge (\epsilon k)^{(1-\epsilon) k}$ for $k$ large given $\epsilon > 0$, and hence $\log N_k \ge (1-\epsilon) k \log k$ when $k$ is large given $\epsilon$. So $\log N_k \sim k \log k$.
The next question to ask is whether $N_k^{1/k}/k$ has a limit, and if so, what is is. We have proven that $\limsup N_k^{1/k}/k \le 16$, but we have not even proven that $\liminf N_k^{1/k}/k > -\infty$.