Well, this is a somewhat standard analytic problem, so I might as well post a solution. By the problem condition, there exists a positive integer $N$ (to be determined later) such that for every $n$, there exists $x_n\in\mathbb{Q}$ satisfying $f(x_n)=f(a^n)^k$. WLOG assume $N$ is large enough so that $f(a^n)$ is nonzero with constant sign and $x_n\ne0$ for $n\ge N$; then $f(x_n)$ must also have a fixed sign for $n\ge N$. By the rational root theorem, there exists a positive integer $\ell$ such that $x_n\ell\in\mathbb{Z}$ for all $n\ge N$. Now suppose $d=\deg{f}>0$, and fix two integers $L,M$ (with $M>L,N$) to be determined later. By Van der Waerden's theorem, there exist positive integers $u,v\ge N$ such that the subsequence $\{x_{u+iv}\}_{i=0}^{M}$ has all terms of sign $\epsilon\in\{-1,1\}$. Let $S=\{u+iv\}_{i=L}^{M}$ (note that we only consider $i\ge L$ here). Lemma 1: There exist constants $A,B,C$ with $A,C>0$ and $A,B\in\mathbb{Q}$ such that $\left|{}|f(x)|^{1/d} - |Ax+B|\right| \le C |x|^{-1}$ for all $x\ne 0$. Proof: Let $r=1/d>0$ and write $f(x)=cx^d(1+F(x))$ (note that $F(x)= O(|x|^{-1})$ only contains the terms $x^{-1},\ldots,x^{-d}$). We can absorb $x$ with small absolute value into the constant $C$, so it suffices to prove the claim for sufficiently large $|x|\ge X$ satisfying $|F(x)|<1/2$. Since $r>0$, the binomial coefficients $\binom{r}{i}$ ($i\ge0$) are bounded in absolute value, so the binomial expansion \[(1+F(x))^r = 1+\binom{r}{1}F(x)+\cdots+\binom{r}{\ell}F(x)^\ell+R_\ell(x)\]for any $\ell\ge \lceil{rd}\rceil=1$ establishes the claim. (Comparing to a geometric series in $F(x)$, we have \[R_\ell(x)=O\left(\frac{F(x)^{\ell+1}}{1-F(x)}\right)=O(F(x)^{\ell+1})= O(|x|^{-\ell-1}),\]as desired.)$\blacksquare$ Corollary: There exists a constant $C'>0$ and positive integer $N>0$ such that for all $n\ge N$, $\left|{}|f(x_n)|^{1/d} - |Ax_n+B|\right| \le C'a^{-kn}$. Proof: The relation $f(x_n)=f(a^n)^k$ implies that there exists a constant $C'>0$ such that for sufficiently large $n$, $C|x_n|^{-1}\le C'a^{-kn}$ for every $n\ge N$.$\blacksquare$ Lemma 2: There exists a polynomial $h\in\mathbb{Q}[x]$ of degree $k$ with positive leading coefficient and a constant $D>0$ such that $\left|{}|f(x)|^{k/d} - |h(x)|\right| \le D |x|^{-1}$ for all $x\ne 0$. Proof: First we mimic the proof of lemma 1 (except with $r=k/d$ and $\ell\ge\lceil{rd}\rceil=k$) to get polynomial $h$ (not necessarily with positive leading coefficient). If $h$ has negative leading coefficient, however, we can just replace it with $-h$.$\blacksquare$ First make $L$ large enough so that $|Ax_n+B| = \epsilon(Ax_n+B)$ for all $n\in S$ (note that $A>0$). Then by the corollary of lemma 1 (take $N$ large enough), \[\left|{}|f(x_n)|^{1/d} - \epsilon(Ax_n+B)\right| \le C'a^{-kn} \le C'a^{-kLv} \le C'a^{-Lv}\]for all $n\in S$. If we also take $L$ large enough so that $h(a^n)>0$ for all $n\in S$ (note that $h$ has positive leading coefficient), lemma 2 gives \[\left|{}|f(a^n)|^{k/d} - h(a^n)\right| = \left|{}|f(a^n)|^{k/d} - |h(a^n)|\right| \le D|a^n|^{-1} \le Da^{-Lv}.\]By the triangle inequality, we thus have \[|\epsilon Ax_n + H(a^{iv})| = |\epsilon(Ax_n+B)-h(a^n)| \le (C'+D)a^{-Lv}\]for all $i\in[L,M]$ (where $n=u+iv$), where $H(x)=\epsilon B - h(a^u x)\in\mathbb{Q}[x]$ is a polynomial of degree $k$ satisfying $\epsilon B - h(a^{u+iv}) = H(a^{iv})$ for all $i\in[L,M]$. Now let $T:i\to i+1$ denote the shift operator and $U(x)=(x-a^0)(x-a^v)\cdots(x-a^{kv})$. Viewing $H(a^{iv})$ as a linear recurrence in $a^0,a^v,\ldots,a^{kv}$ indexed by $i$, we have $U(T)(H(a^{iv}))=0$ for $i\in[L,M-k]$, so again by the triangle inequality, \begin{align*} |U(T)(\ell\ell' Ax_{i+uv})| &\le \ell\ell'(C'+D)a^{-Lv}(a^0+1)(a^v+1)\cdots(a^{kv}+1) \\ &\le \ell\ell'(C'+D)2^{k+1}a^{v(k(k+1)/2-L)}, \end{align*}where $\ell'$ is the smallest positive integer such that $\ell'A\in\mathbb{Z}$ (clearly $\ell'$ is independent of $L,M$). Since $\ell,\ell',C',D,k$ are all constants independent of $L,M$, we can choose $L$ large enough so that the RHS is strictly less than $1$, and then choose any $M\ge L+k+2dk$. But then $|U(T)(\ell\ell' Ax_{i+uv})|\in\mathbb{Z}$ must in fact be zero, so there exists a polynomial $G\in\mathbb{Q}[x]$ of degree $k$ (corresponding to a linear recurrence in $a^0,a^v,\ldots,a^{kv}$) such that $x_{u+iv}=G(a^{iv})$ for $i\in[L,M-k]$. Finally, if we take $g(x)=G(xa^{-u})\in\mathbb{Q}[x]$, then $x_n=g(a^n)$ for $M-k-L+1\ge 2dk+1$ values of $n$, whence $f(g(x))-f(x)^k$ (which has degree $\le dk$ yet vanishes for at least $2dk+1$ values of $x$) must be identically zero, as desired. Note: This is also true for integers $a\le -2$, as we can just restrict ourselves to even $n$.

Perhaps I should give some background: I originally came up with the problem by overkilling an Iran TST problem (while working through Problems from the Book). (As harazi notes in the thread, the constraints there are rather excessive.) Now that I am slightly less blind than before, I see that my problem can be easily generalized (with basically the same solution) to the following more natural version: Fix two positive integers $a,k\ge2$, and let $f,p\in\mathbb{Z}[x]$ be two nonconstant polynomials. Suppose that for all sufficiently large positive integers $n$, there exists a rational number $x$ satisfying $f(x)=p(a^n)^k$. Prove that there exists a polynomial $g\in\mathbb{Q}[x]$ such that $f(g(x))=p(x)^k$ for all real $x$. Then it becomes a direct generalization of, for instance, the classic Bulgaria problem, except this time we need the more technical (but only slightly) lemma 2 in addition to lemma 1.