Untested, but using Counter from collections may be quicker than forming a set of the last k values each time.
counter = collections.Counter(m)
for j in xrange(n - k):
i = 0
while counter[i]:
i += 1
counter[m[j]] -= 1
counter[i] = 1
m.append(i)
If making the counter takes a long time because k is very large, you could consider making it in 'chunks', reading say the smallest 100 values from m initially then reading another 100 only when i gets larger than the smallest 100.