I could not really follow up on the hints of using $|B_t|. $ However, while I am quite "green" in the matter of Markov processes, I am better at using conditional expectations. So, here is my argument that uses the Freezing Lemma, sometimes called even the Independence Lemma (I always wondered what it was useful for and finally I have my answer, albeit 15 years or more after I studied it!).... Here it goes:
Let $f: R^2 \mapsto R $ be a measurable and bounded function. Then, for $0 \le s \le t: $
\begin{equation*}\begin{split}
E[f(B_t, M_t) \mid {\cal F}_s] &= E[f(B_s + (B_t-B_s), M_s \vee \sup_{s \le u \le t} B_u) \mid {\cal F}_s]\\
&= E[f(B_s+ (B_t-B_s), M_s \vee \{B_s + \sup_{s\le u\le t} (B_u-B_s)\}) \mid {\cal F}_s].
\end{split}\end{equation*}
At this point, we should recognize that $M_s $ and $B_s $ are ${\cal F}_s$-measurable and that $B_t-B_s $ and $B_s + \sup_{s\le u\le t} (B_u-B_s) $ are instead independent of $ {\cal F}_s $ and an application of the Freezing Lemma yields that
$$ E[f(B_t, M_t) \mid {\cal F}_s] = g(B_s, M_s) $$
where
$$ g(x, y) := E[f(x+ y \vee \sup_{s\le u \le t} (B_u -B_s), x+ (B_t-B_s))]. $$
Hence $(B, M) $ is a Markov process.
I wonder if, by trying to prove the results using transition kernels could use the the fact that $M_t $ and $|B_t| $ have the same distribution
PS... On an unrelated issue... what happened to guys like Did, Saz and other mathematicians of high stature that used to have an asnwer to almost anything? Are they no longer associated with the website?