As input we are given a string $s$ comprising $n$ tokens from a vocabulary of size $m$. We are asked to count the number of strings from the same vocabulary that are at a particular edit distance of $k$ away from $s$.
Is there an efficient algorithm in $n$, $m$, and $k$ for this problem?
You can look into Levenshtein automaton. The main references are Fast String Correction with Levenshtein-Automata by Schulz and Mihov and Deciding word neighborhood with universal neighborhood automata by Mitankin, Mihov, and Schulz. There is an implementation called liblevenshtein which you can play with online here.
This algorithm gives you all words at distance at most $k$ from your string. So to get words that are at distance exactly $k$ you must remove the words at distance less than or equal to $k-1$.
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
