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 that 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$ &mdash; 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$ &mdash; then by the inductive hypothesis, for sufficiently large $k$ we have $F^{k+1}(x) \equiv G(F^k(x)) ~\text{mod}~ m$ and 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 &mdash; it's simply a generalization of the observations in Update #1.

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.