Let $t \gt 0$ be an integer and $G$ is a simple graph with $\chi_f(G) = t$. Then $t$= inf $\{ \frac{n}{k}| G \rightarrow KG(n,k)\}$ where $KG(n,k)$ is the Kneser graph.
Does there exist a $k$ such that $G \rightarrow KG(tk,k)$? If so, what is the complexity of finding such a $k$?
Bondy and Hell, in their paper on the star chromatic number, prove that $$ \chi_f(G) = \min \left\{ \frac{n}{k}: G\to KG(n,k) \right\} $$ Note that we have $\min$ here, not $\inf$. So the answer to your first question is yes. The proof of this result in my favorite book on Algebraic Graph Theory (which I am pretty sure follows that of Bandy and Hell) constructs the required homomorphism from the fractional coloring. Hence I suspect that the answer to your second question is that it is hard to determine the minimum value of $n$ needed. (But I do not know, and I do not recall seeing anything on this point.)
