Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
What you are interested in are semi-global and/or local alignments. The usual way to compute those is to adapt the dynamic programing algorithm for the Levenshtein distance:


Initialise the first row/column with $0$ (instead of $i$/$j$) if free deletions/insertions are allowed at the beginning.
Select the minimum value from the last row/column as result if free deletions/insertions are allowed at the end.


Different combinations are possible. In your case, assume that $r$ is the horizontal word, you initialise the first row with $0$ (the first column with $i$, no change here) and the result is the minimum of the last row. The result is then the smallest Levenshtein distance between $s$ and any substring of $r$, computed in time and space $O(nm)$.

Now, in order to get scores for all starting positions, note that the computation of semi-global alignments with allowed deletions/insertions at the end conveniently provides the wanted array in the last row/column -- well, almost: that gives you the best matches against prefixes up to position $k$. So in order to get best matches against suffixes from position $k$, reverse both $r$ and $s$.