This is not really an answer, just a (very!) long comment. Everything I write is obvious for people working in Iwasawa theory, and I apologize for the trivialities.
Let me start by your final paragraph, where you discuss the analogy with curves over finite fields and the action of Frobenius: I guess you are aware that this was one of the motivations for Iwasawa theory, and this is discussed a bit in Washington's book, Chapter 13 (both in the introductory paragraph and in 13.6). But my feeling is that $V$ is somehow analogous to a $p$-adic theory (like crystalline, or overconvergent), rather than étale $l$-adic: in the analogy, we consider $K_\infty/K_0$ as the constant field extension, which has only one Frobenius. What changes in the rationality business are the coeffients: here, your coefficients are always the same, and $p$-adic, and you change "Frobenius".
Passing to your question, anyhow, let me stick for notational ease to the case $n=p$ and write $K_\infty=\varinjlim \mathbb{Q}(\zeta_{p^{k+1}})$. The Galois group $\operatorname{Gal}(K_\infty/K_0)$ is procyclic, isomorphic to $1+p\mathbb{Z}_p$ through the cyclotomic character $\kappa\colon\operatorname{Gal}(K_\infty/K)\to 1+p\mathbb{Z}_p$ (or rather its inverse, to be consistent with your choice): let me fix a topological generator $\gamma_0$ of this Galois group which, for notational ease, I suppose to be sent via $\kappa$ to the element
$(1+p)\in(1+p\mathbb{Z}_p)$.
Introduce the logarithm $\mathcal{L}$ "in base $1+p$"
$$
\mathcal{L}(u)=\frac{\log_p(u/\omega(u))}{\log_p(1+p)}%\quad\text{ and }\quad (\mathbb{Z}/p)^\times\ni\ell\colon x\mapsto 1\in\mathbb{Z}/(p-1)
$$
where $\log_p$ is Iwasawa's $p$-adic logarithm, $\omega$ is the$\mod{p}$ Teichmüller character, and $u\in\mathbb{Z}_p^\times$. Then, for every integer $q\not\equiv 0\pmod{p}$ we have $f_q=\gamma_0^{%-\ell(\omega(q))+
\mathcal{L}(q)}$.
Now, if the action of $\gamma_0$ is semi-simple, then the matrix of $\gamma_0$ acting on $V\otimes \overline{\mathbb{Q}}_p$ is
$$
M_{\gamma_0}=\begin{pmatrix}\alpha_1&&\\&\ddots&\\ &&\alpha_{\lambda}\end{pmatrix},
$$
where the $\alpha_i$'s are the roots of the characteristic polynomial, and then $\operatorname{Tr}(\gamma_0)=\alpha_1+\dots+\alpha_\lambda$. By the above remark, $\operatorname{Tr}(f_q^\ast)=\alpha_1^{%\omega^{-1}(q)
\mathcal{L}(q)}+\dots+\alpha_\lambda^{%\omega^{-1}(q)
\mathcal{L}(q)}$ and to address your question it seems natural to start studying these roots $\alpha_i$'s themselves. The first thing we can observe is that $\alpha_i\equiv 1\pmod{\mathfrak{m}_{\mathbb{C}_p}}$ because $\gamma_0$ is topologically unipotent and thus $\lim_{n}\alpha_i^{p^n}=1$. Moreover, by definition, $$\alpha_i^{\mathcal{L}(q)}=\exp_p(\log_p(\alpha_i)\mathcal{L}(q))=\exp_p\Bigl(\log_p(\alpha_i)\frac{\log_p(q/\omega(q))}{\log_p(1+p)}\Bigr);
$$
I am not an expert in $p$-adic transcendence, but granted that $q/\omega(q),(1+p)$ and $\alpha_i$ are algebraically independent (for non-pathological $\alpha_i$), I would be surprised if the above expression were algebraic.
To go further, observe that $V$ is actually a direct sum $V^+\oplus V^-$ of two subrepresentations, which are the $\pm$-eigenspaces for the action of the complex-conjugation $c\in\operatorname{Gal}(K_\infty/K_0)$. A well-known conjecture by Greenberg predicts that $V^+=0$ (this has been checked numerically in many cases), so it is natural to restrict only to the subspace $V^-$. Greenberg himself has proven in his paper On a certain $l$-adic representation (Invent. Math., 1973) that the action of $\gamma_0$ on $V^-$ is semi-simple and that its minimal polynomial is $f_{\gamma_0}^-(T)=(T-1)^sg(T)$ where $s$ is the number of primes above $p$ in $K_0^+$ which split in $K_0$: so, in our case $n=p$ we have $s=0$ and $\alpha_i\neq 1$ for all $i$. The roots of $f_{\gamma_0}^-(T)$ (again, conjecturally $f_{\gamma_0}^-(T)=f_{\gamma_0}(T)$ because $V^+$ should be $0$) are connected, via the Main Conjecture of Iwasawa Theory (now a theorem), to the zeros of the $p$-adic $L$-function $L_p(s,\chi)$ of Kubota--Leopoldt, where $\chi$ runs through all even characters of $\operatorname{Gal}(K_0/\mathbb{Q})$. This goes as follows: the representation $V^-$ can be further decomposed as $V^-=\oplus_{\chi}V(\chi^{-1}\omega)$ where $\chi$ are the even characters of $\operatorname{Gal}(K_0/\mathbb{Q})$ and $V(\chi^{-1}\omega)$ is the subspace on which the action of $\operatorname{Gal}(K_0/\mathbb{Q})$ is given by $\chi^{-1}\omega$: accordingly, $f_{\gamma_0}^-(T)=\prod_\chi f(T,\chi)$. Then Mazur--Wiles and Rubin have proven that $L_p(s,\chi)=f((1+p)^s,\chi)$ and thus if $\alpha_i$ is a root of $f_{\gamma_0}^-(T)$, then $f(\alpha_i,\chi)=0$ for some $\chi$ and $L_p(\mathcal{L}(\alpha_i),\chi)=0$; and conversely, if $L_p(s_0,\chi)=0$ then $(1+p)^{s_0}$ is a root of $f(T,\chi)$ and hence of $f_{\gamma_0}(T)$.
Now comes the sad side of the story, namely that (in Washington's words, see the Remark following Theorem 5.11 in his book Introduction to Cyclotomic Fields) "the nature of the zeros of the $p$-adic $L$-function is not yet understood". Computations by Ernvall and Metsänkylä show that, in general, the $\alpha_i$ are not rational numbers, because the $p$-adic valuation of $\alpha-1$ is non-integral (see Propositions 4 and 5 in their paper Computation of the zeros of $p$-adic $L$-functions, Math. Comp., 58, 1992). It is worth quoting the final sentence of the paper:
On the basis of the numerical data computed so far it seems natural
to expect that the zeros $T_j$ (corresponding to my $\alpha_j-1$)
and $s_i$ (corresponding to my $\mathcal{L}(\alpha_i)$) are distributed
randomly as regards their $p$-adic value (within the prescribed
limits) and their inclusion in various extensions of $\mathbb{Q}_p$.
Also the $p$-adic expansions of the zeros fail to show any regularity.
Remark I have chosen a highly non-standard normalization, so if you look at the litterature, pay attention: in particular, what is called $f(T)$ is normally the characteristic polynomial of $\gamma_0-1$ rather than of $\gamma_0$.