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).$$