It's as simple as "the composition of hypergeometric functions is not hypergeometric". $f(n)=2^n$ is a hypergeometric function because $f(n+1)/f(n)=2$ is a rational function of $n$, but $g(n)=(f\circ f)(n)=2^{2^n}$ satisfies $g(n+1)/g(n)=2^{2^n}$ which obviously grows much too fast to be rational.

Have you tried throwing Gosper's algorithm/WZ at it? That may not give the combinatorial proof but it certainly should serve to prove the relation.

Is it even clear that the (suitably scaled) distribution of $Z(\sigma_{2n})$ over all words of length $2n$ converges to a normal distribution?

This puts the lemniscate orthogonal to the circle — in the $xz$ plane, as opposed to the $xy$ plane the original circle is in. I think OP is looking for a $180^\circ$ twist. (Though I suppose composing this with a rotation of $t$ about the x axis will do it.)

I did not downvote, but a few more notes on why you might have gotten downvoted, things that suggest this question is not research-level: (1) your definition of $\pi_n(N)$ has the condition $x\in D(n)\cap[n]$, but trivially $D(n)\subset [n]$, so the intersection isn't needed. (2) Of the conjectured properties of $\pi$ that you mention, the second one is trivial and the first and third are almost trivially false: $\pi_8(7)=4$ and $\pi_5(8)=5$. Perhaps you mean $\pi_n(N)\mid n$? But this is also trivial, since the domain over which the max is taken is just the divisors of $n$.

Quick check: where you write $\mathbb{Z}/2$, do you want $\mathbb{Z}/2\mathbb{Z}$? Or is this a standard shortening that I'm not familiar with?

I think you might have either a typo or thinko — above the tree you mention querying a number about its smallest prime divisor, but the way you recurse suggests that the key quantity is actually the number's largest prime divisor. You do eventually get to the smallest at the top level by stripping away all the larger ones, but every arrow from one level to the next is actually a multiplication by that largest prime divisor.

You didn't have a typo — my first edit did (an incorrect factorization), and I made a second edit to fix my mistake but they may have been folded into one. And you're very welcome!

And one (semi)trivial answer to the latter question: the family of one-relator groups, where it's relatively straightforward to decide if the presented group is free.

I think what ThorbenK is asking about is whether there are interesting sufficient criteria. Undecidability dictates that there aren't necessary and sufficient ones, but that doesn't mean that each individual case is undecidable, or even that there aren't algorithmically decidable families of presentations.

Another question related to the issues of complexity: since the Angel wins it's hard to speak of an 'optimal' strategy for the Devil, but let's assume that D's goal is to (asymptotically) minimize $\max(|p|)$. What's the diameter of the Devil's 'working space'; i.e., given that $n$ moves have happened, what's the max of $|x|$ that a Devil needs to consider for good moves under some metric of good?

I presume because the answer is comfortably 'no one believes it but we have no idea how to prove it as of right now'.

I think this is my favorite because you could write it out for an undergrad or even advanced high school student and have them understand the claim.