Analogue of decay of Fourier coefficients of a smooth function on $mathbb{S}^1$

Here is a second example where a given basis fails to do the job. If $mu$ has, say, a continuous positive density, then there a homeomorphism $h$ that sends $(mathbb S^1,mu)$ to $(mathbb S^1,nu)$ (uniform), in the sense $h^*nu=mu$. Now because of the result you cite, the usual basis $(phi_n)$ in $(mathbb S^1,nu)$ detects $mathcal C^k$ functions according to your criterion, hence its preimage $(phi_ncirc h)$ in $(mathbb S^1,mu)$ detects functions $f$ such that $fcirc h$ is $mathcal C^k$. If $h$ is not $mathcal C^k$ (i.e. the density of $mu$ is not $mathcal C^{k-1}$, I suspect), then you will have functions satisfying your criterion but are not smooth.

If the density $rho$ such that $mathrm dmu=rhomathrm dnu$ is bounded above and below, then I believe $(I_ncdotphi_n/rho)$ will do the trick, with $1/I_n=|phi_n/rho|^2$.

In general it is not true. Let ${f_n}_{ngeq 1}={1,z,overline{z},z^2,overline{z^2},ldots}$, then as the OP pointed out $a_n=o(n^{-k})$. However, with a suitable permutation $sigma$ of the basis ${f_n}_{ngeq 1}$, we will have that coefficients in this new basis satisfy $tilde{a}_n=a_{sigma(n)}$. We can choose $sigma$ so that for infinitely many $n$, $sigma(n)gg n$.Then it might happen for such $n$ that $$ frac{tilde{a}_n}{n^k}=frac{a_{sigma(n)}}{sigma(n)^k}left(frac{sigma(n)}{n}right)^kto infty. $$ Indeed, although $a_{sigma(n)}/sigma(n)^k$ is small, $(sigma(n)/n)^k$ might be very large. Providing a more explicit example from this sketch is now a simple exercise.