Lexicographic permutation
First, there is one special case of $k$, the powers of 10, which are 1, 10, 100, etc. Their positions at a lexicographically ordered sequence of positive integers are fixed.

1 is always at the 1st position.
10 is always at the 2nd position once it appears. Any number except 1 and itself will be sorted after it.
100 is always at the 3rd position once it appears. Any number except 1, 10 and itself will be sorted after it.
And so on.

We should process this peculiar case first.
The position of $k$ in the lexicographically sorted sequence is determined by the numbers that are before $k$ (lexicographically). These numbers fall into three categories.

the numbers that are smaller than $k$. If a permutation of 1, 2, ..., $n$ contains $k$, it must contain all these numbers as well.
$k$ itself.
the numbers that are bigger than $k$.

Let us compute how many numbers before $k$ are smaller than $k$. For example, take k $=$ 619. Any number smaller than $k$ has at most three digits.

All three-digit numbers before 619 constitute the interval [100, 619).
All two-digit numbers before 619 constitute the interval [10, 61].
All one-digit numbers before 619 constitute the interval [1, 6].

In total, there are 519 + 52 + 6 $=$ 577 numbers that are smaller than 619 and before 619. So if $m\le$ 577 + 1, where 1 stands for 619 itself, no $n$ can satisfy $Q(n,\,$619$)=m$. If $m=$ 578, the minimum $n$ is 619 itself.
Otherwise, the given $m$ is bigger than 1 plus the number of numbers smaller than $k$ and before $k$. We have to include numbers bigger than $k$ that are before $k$ to increase the position of $k$. For the same example, when $m\gt 578$, $n=$ 619 is not enough.

Try adding the number between 1000 inclusive and 6190 exclusive.
If that is not enough, try adding the number between 10000 inclusive and 61900 exclusive.
If that is not enough, try adding the number between 100000 inclusive and 618900 exclusive.
And so on.