What is the significance of the power of $3$ in the sequence of primes given by $\lfloor A^{3^n}\rfloor ?$

The $\lfloor A^{3^n}\rfloor$ thing sounds impressive, but it's really not. It follows quickly from the (much more impressive) fact that for any sufficiently large integer $N$, there's always a prime between $N^3$ and $(N+1)^3$.

Given that fact, here's Mill's proof of his constant. It's only one page long, and doesn't use any difficult math. The idea is to restrict $A$ to a small interval, and make the interval smaller and smaller in a series of steps.

At each step, there's a certain range that $A^{3^n}$ can be in. For that step, choose a prime $p$ in that range, and then restrict $A$ to a slightly smaller interval so that everywhere in the new interval, $\lfloor A^{3^n}\rfloor$ equals $p$. Since the function $x^{3^n}$ grows so fast, you know that the new range for $A^{3^{(n+1)}}$ is so large that it must include a prime number, so you can keep going to the next step. That observation follows from the impressive fact above, and it's the reason for the "3". If you continue this process forever, you'll get more and more accurate values for $A$.

So to answer your related questions:

$\lfloor Q^{k^n}\rfloor$ always works if $k$ is at least 3. The same argument shows there must exist such a $Q$.

But $\lfloor Q^{2^n}\rfloor$ might not work. It depends on the following open conjecture: is there always a prime between $N^2$ and $(N+1)^2$? This is known as Legendre's conjecture, and it's thought to be extremely difficult.