I'll assume you are using an edit distance that can be computed in polynomial time and that the reverse of an edit is also an edit. Also, for any string there are only a polynomial number of possible edits. Then, reverse search will take time that is polynomial in the number of output strings, even if $k$ is an increasing function of $n$.

Define an order (say, lexicographic order) on the edits that can be made to a string. Call this with argument $s$:

**procedure** search(string t) Output $t$; **if** dist$(t,s) < k$ **then** **for** each string $u$ obtained by applying one edit to $t$ **do** **if** dist$(u,s)$=dist$(t,s)+1$ and $t$ is the result of applying the lexicographically least edit to $u$ **then** search($u$) **endif** **endfor** **endif** **endprocedure**