Just use the usual Cramer rule for the inverse of $A+kI$. This shows that $f(k)$ is a rational function of $k$ with degrees of numerator and denominator bounded by $N$, which you can find, e.g. numerically, by Pade approximation.
More sophisticated techniques, used in combinatorics, for tackling this kind of stuff, are called "transfer matrices". See e.g. Vol.I of R. Stanley's book, where in the 2nd edition, available online, it starts on p.573.
EDIT: while numerically this might not be optimal, at least this tells you upfront what kind of function you are dealing with. And if you're only interested in the asymptotic behaviour of $f(k)$ for large $k$, then with a bit of luck you might not even need to compute the full rational form expression for $f(k)$.
