I have a function of the form
$$ f(k)=\frac{1}{a_1-a_{2}k^2e^{-(a_{3}-a_{4}k^2)}};\quad k=0...n$$
I approximated it with Taylor series expansion around $k=\frac{n}{2}$, but the results is not very precise (transformation of the function in order to obtain different intervals on the argument, e.g. $[0,1]$ did not work well either).
Are there other general-purpose polynomial expansions in place that yield sharper bounds?
Your problem is probably caused by the fact that the denominator can go to zero and polynomials do not fit poles well. Even if your $a$'s are such that the denominator cannot go to zero, nearby poles in the complex plane can ruin your day. You might be interested in a rational function (a ratio of polynomials) instead. There should be any information in any numerical analysis book. Section 3.2 of Numerical Recipes discusses this and the obsolete versions are free.