Untested, but using deque and Counter from collections should be quicker than forming a set of the last k values each time, for large values of k and n.
last_k = collections.deque(m)
counter = collections.Counter(m)
for j in xrange(n - k):
i = 0
while counter[i]:
i += 1
counter[last_k.popleft()] -= 1
counter[i] += 1
last_k.append(i)
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.