First notice that $\frac{2k+1}{n+k+1}\binom{2n}{n-k} = \frac{2k+1}{2n+1}\binom{2n+1}{n-k}$.
To prove that $F_n(q)$ is a polynomial it is enough to show that
$$\sum_{k=0}^n(-1)^k(2k+1)\binom{2n+1}{n-k}\frac{q^k}{1+q^{2k+1}}$$
has the zero $q=1$ of multiplicity $2n$.
Plugging $q=e^t$, one needs to show that
\begin{split}
&\frac{e^{-t/2}}{2}\sum_{k=0}^n(-1)^k(2k+1)\binom{2n+1}{n-k}\mathrm{sech}(\frac{2k+1}2t)\\
=& \frac{e^{-t/2}}{2}\sum_{k=0}^n(-1)^k(2k+1)\binom{2n+1}{n-k} \sum_{l\geq 0} \frac{E_{2l}(\frac{2k+1}2t)^{2l}}{(2l)!}\\
=& \frac{e^{-t/2}}{2} \sum_{l\geq 0} \frac{E_{2l}t^{2l}}{2^{2l}(2l)!}\sum_{k=0}^n (-1)^k\binom{2n+1}{n-k} (2k+1)^{2l+1}
\end{split}
has the zero $t=0$ of multiplicity $2n$, where $E_{2l}$ are Euler numbers. So, the problem boils down to proving that
$$(\star)\qquad\sum_{k=0}^n (-1)^k\binom{2n+1}{n-k} (2k+1)^{2l+1} = 0\quad\text{for all }l<n.$$
Proof of $(\star)$.
Let us notice that the l.h.s. of $(\star)$ is nothing else but $(-1)^n$ times the coefficient of $x^{2n}$ in the polynomial
$$f(x):=(1-x^2)^{2n+1} \frac{A_{2l+1}(x)}{(1-x)^{2l+2}}=(1+x)^{2n+1}(1-x)^{2n-2l-1} A_{2l+1}(x),$$
where $A_{2l+1}(x)$ is Eulerian polynomial. It is crucial to notice that both $(1+x)^{2n+1}$ and $A_{2l+1}(x)$ are palindromic polynomials and so is their product, while $(1-x)^{2n-2l-1}$ is an antipalindromic polynomial. It follows that $f(x)$ is also antipalindromic, and since $\deg f(x)=4n$, we have $[x^{2n}]\ f(x)=0$.
QED
