This answer is incomplete and potentially misleading, so I'm posting an extended comment.
First of all, there is something wrong with the OP's formula. The left hand side is a probability which is a non-random number while the right hand side depends on the random variable $X(m)$. Probably what he means is
$$ P\big(X(m+1)=j\,|\, X(m)\big)= \cases{ \frac{X(m)}{n}&\text{if $X(m)=j$}\\[3pt] 1-\frac{X(m)}{n}&\text{if $X(m)=j-1$}\\[5pt] 0 &\text{otherwise}.}$$
This formula describes the conditional distribution of $X(m+1)$ given $X(m)$. By definition, this depends only on $X(m)$ and not $X(m-1),\dots, X(1), X(0)$, and this is true whether or not the process $X$ satisfies the Markov property.
The OP is correct in asserting that to prove the Markov property, you must consider conditional probabilities of the form $$P(X(m+1)=j\,|\,X(m)=K_m,\ldots ,X(0)=K_0),$$ or alternatively joint probabilities of the form $$P(X(m)=K_m,\ldots ,X(0)=K_0).$$
For the coupon collector's problem, this is a bit of a pain, but it is not terribly difficult and it has to be done to prove that $X$ is Markov.
Added: Here is a simple example that maybe explains my objection a bit better.
Draw cards one at a time, without replacement, from a well-shuffled deck. For $1\leq n\leq 52$, let $X_n$ be the color of the card drawn at time $n$. This is a stochastic process with state space ${\cal S}=\{R,B\}$.
For $1\leq n <52$, using exchangeability you find that $\mathbb{P}(X_{n+1}=j\,|\,X_n=i)$ is the $(i,j)$th entry in the matrix
$$P= \pmatrix{{25\over 51}&{26\over 51}\\[3pt] {26\over 51}&{25\over 51}}.$$
So $(X_n)$ is time homogeneous, and has a "transition matrix" $P$ but, nevertheless, it is not Markov.
Why not? Well, for example $$\mathbb{P}(X_3=B\,|\,X_2=R,X_1=R)={26\over 50}\neq {26\over 51}=\mathbb{P}(X_3=B\,|\,X_2=R).$$