(**Edit :** added something for big values of $s$).

An easy upper bound that generalizes Kesten's bound is given by $(\sqrt{2k-1}/k)^{2\ell} \sqrt{N_s}$ where $N_s$ is the number of reduced words of length at most $2s$. As noted in the comments, this in only interesting if $s$ is not to close to $\ell$.

Proof: Let $A$ denote the generator of the random walk on $F_k$, i.e. $A = \frac{1}{2k} \sum_{i=1}^k \lambda(g_i) + \lambda(g_i^{-1}) \in B(\ell^2 F_k)$, $\lambda$ is the left regular representation. To avoid confusion I denote by $|\cdot|$ the norm in $\ell^2 F_k$ and $\|\cdot\|$ the operator norm on $B(\ell^2 F_k)$. Then Kesten's theorem is that $\|A\|=(\sqrt{2k-1}/k)$. And the probability you are loooking for is $\langle A^{2\ell} \delta_0,\sum_{|\omega|\leq 2s} \delta_\omega\rangle$, which is less than $\|A^{2\ell} \| |\delta_0| |\sum_{|\omega|\leq 2s} \delta_\omega| = (\sqrt{2k-1}/k)^{2\ell} \sqrt{N_s}$.

For large values of $s$, you can get asymptotic results by combining the law of large numbers and the central limit theorem.

Indeed, there is a natural coupling for different values of $\ell$ (consider the uniform probability on infinite sequences of elements of the alphabet, and for each $\ell$ only remember the first $2\ell$ letters), and if $d_\ell$ is the random variable denoting the half of the length of a word of length $2\ell$, you have that $d_{\ell+1} - d_\ell$ is equal to $-1,0$ or $1$ with probability $1/4 k^2$, $(2k-1)/2k^2$ and $(2k-1)^2/4k^2$, unless $d_\ell = 0$. But Kesten's bound shows that we can forget this "unless" and work in the ideal random walk on $\mathbb R$ model, and apply the law of large numbers and the central limit theorem. Namely the probability that $d_\ell$ is less that $((k-1)/k) \ell + C \sqrt \ell$ has an explicitely computable limit for every $C$. In particular the probability that $d_\ell<\alpha \ell$ goes to zero if $\alpha<(k-1)/k$, and $1/2$ if $\alpha=(k-1)/k$ and $1$ otherwise.

If you want some more precise results (eg if $s/\ell \to \alpha < (k-1)/k$), a naive guess would be to apply large deviation techniques. But one should be careful and take into account the "unless $d_\ell = 0$".

ishard to tell. Even with glasses, which I wear since childhood. Worse, indices tend to occur in subscripts, in smaller font. Classic example: l and I in Computer Modern, the default (La)TeX font. I find $C_I$ and $C_l$ difficult to distinguish there (and on this website, too). Yes I can distinguish them when focusing, but a single mixup when reading can cause lots of confusion. Hence many people use \ell instead of l. If you have a better solution (note that you usually can't choose fonts in journals), please tell! – Max Horn Jul 18 '12 at 11:16