@VítTuček: No, I did not. Could you please elaborate a little more on this?

Since I'm not familiar with Paley-Wiener theorem, could you suggest a good reference on this? Thanks.

I see, thanks. So, assuming that I could get rid of the $e^{n\epsilon}$ term, what I get is the upper bound $I(n)\le (k-\sqrt{k^2-1})^{2n}$. Is it possible to show that such a bound is tight? (btw, I'm not completely sure about the $\sqrt{n}$ factor: it's just a numerical guess)

Thanks! One quick question: what does $\lesssim_\varepsilon$ mean?