I believe that the statement is still true even if we let $b>(|a|+1)^d$

Post for storage. Let $u_n=f(n)\cdot a^n$. After trying $d=0,1$, the idea become clear: Try to find some relation between $u_n,u_{n+1},\dots,u_{n+d+1}$. First, by Lagrange interpolation, we have that: $$\sum_{k=0}^{d+1}(-1)^k\binom{d+1}{k}f(n+k)=0$$ Hence, by multiplying $a^{n+d}$, we have that: $$ \sum_{k=0}^{d+1}(-1)^k\binom{d+1}{k}a^{d-k} u_{n+k}=0$$From above, we also have that: $$ \sum_{k=0}^{d+1}(-1)^k\binom{d+1}{k}a^{d-k} \lfloor u_{n+k}\rfloor=\sum_{k=0}^{d+1}(-1)^{k+1}\binom{d+1}{k}a^{d-k} \{u_{n+k}\}$$Recall that we have $\lfloor u_{n}\rfloor \equiv \lfloor u_{n+p}\rfloor \pmod{b}$ for all large $n$. Hence, it holds that: $$\sum_{k=0}^{d+1}(-1)^{k+1}\binom{d+1}{k}a^{d-k} \left(\{u_{n+k+p}\}-\{u_{n+k}\}\right) \equiv 0 \pmod{b}$$However, it is easily to see that $$|LHS|\leq \sum_{k=0}^{d+1}\binom{d+1}{k}|a|^{d-k} \le (|a|+1)^{d+1}$$Hence, LHS must be equal to $0$ since $b \geq (|a|+1)^{d+1}$. Let $v_n=\{u_{n+p}\}-\{u_{n}\}$, then we have that $v_n \in (-1,1)$ and $$\sum_{k=0}^{d+1}(-1)^{k+1}\binom{d+1}{k}a^{d-k} v_{n+k} = 0 $$By recurrence, there is a polynomial $p$ of degree at most $d$ such that $v_n=a^n\cdot p(n)~\forall~n$. Hence $v_n=0~\forall~n$. Hence, it holds that $\{u_{n+p}\}=\{u_n\}~\forall~n$. Finally, since $u_{n+p}=a^p\cdot u_n$, we have $$\lfloor u_{n+p}\rfloor-a^p\lfloor u_{n}\rfloor=(a^p-1)\cdot \{f(n)\cdot a^n\}$$Thus, $f(n)\cdot a^n \in \mathbb{Q}~\forall ~n$ and so does $f(n)$. Finally, since $f(n) \in \mathbb{Q}~\forall~n$, we have that $f(x) \in \mathbb{Q}[x]$ by Lagrange interpolation, as desired.

Let $x_n = \lfloor f(n)a^n\rfloor$. By the condition, there exist some $N, T$ such that for all $n \geq N$, $x_{n+T} \equiv x_n \pmod b$. Then \[f(n+T)a^{n+T} - f(n)a^n -(x_{n+T}-x_n) \in [-1, 1].\]In particular, denote $g(n) = f(n+T)a^T - f(n)$, and $d = \deg g$, so \[a^n g(n) - (x_{n+T}-x_n) \in [-1, 1].\]Also, \[\sum_{i=0}^{d+1} {d+1 \choose i} (-1)^i a^{n+i} \cdot g(n+i) \cdot a^{d+1-i} = 0.\]This follows because by factoring out $a^{d+1+n}$, we get a partial difference expression for the $d+1$th partial difference of the polynomial $g$ with degree $d$, which is obviously zero. Combining this with previous results, \[\sum_{i=0}^{d+1} a^{d+1-i} {d+1 \choose i} (-1)^i\left(a^{n+i} g(n+i) - (x_{n+T+i}-x_{n+i})\right) = 0\]because the quantity is clearly $0$ mod $b$ and $b \geq (|a| + 1)^{d+1}$, hence it is less than $b$. It follows that \[\sum_{i=0}^{d+1} a^{d+1-i}{d+1 \choose i}(-1)^i (x_{n+T+i}-x_{n+i}) = 0.\]But then the sequence $\{x_n\}$ is recursive with degree $d+2$, and in particular its characteristic equation is given by exactly $(x-a)^{d+2}$. Hence we have \[x_n = a^n \cdot h(n) + x_0\]for some polynomial $h$ of degree $d$ and all $n \geq N$. In particular, the $d+1$ coefficients of $h$ and $x_0$ are the solution to the nonsingular system of equations given by taking $n = N, N+1, N+2, \dots, N+d+1$ with rational coefficients, so $h$ has rational coefficients. In particular, \[x_{n+T+i}-x_{n+i} - a^{n+i}g(n+i) = a^{n+i}(h(T+n+i)a^T - h(n+i) - g(n+i)) \in [-1, 1].\]It follows that the polynomial $h(T+n+i)a^T - h(n+i) - g(n+i)$ is bounded as a polynomial in $n$, hence it must be the constant and thus the zero polynomial. Then \[f(n+T+i)a^T - f(n+i) =g(n+i) = h(n+T+i)a^T - h(n+i)\]for all $n \geq N$, implying $f \equiv h$. So $f$ is a polynomial with rational coefficients.