Here are two examples, in discrete time and in continuous time, hopefully not too close from each other.
1. The process of the running maxima of a Markov process is in general not Markov.
1.1 Consider your favorite Markov process, say the standard symmetric random walk $(X_n)_{n\geqslant0}$ on the integer line, defined by $X_0=0$ and $X_n=Y_1+\cdots+Y_n$ for every $n\geqslant1$, where $(Y_n)_{n\geqslant1}$ is i.i.d. and symmetric Bernoulli, hence $\mathrm P(Y_n=1)=\mathrm P(Y_n=-1)=\frac12$.
The process of the running maxima of $(X_n)_{n\geqslant0}$ is the process $(M_n)_{n\geqslant0}$ defined by $$M_n=\max\{X_k\,;\,0\leqslant k\leqslant n\}.$$ Then:
The process $(M_n)_{n\geqslant0}$ is not a Markov process, nor a Markov process of any higher order.
To see this, note that $M_{n+1}$ is either $M_n$ or $M_n+1$, and that the probability that $M_{n+1}=M_n+1$ depends on $$T_n=\max\{0\leqslant k\leqslant n\,;\,M_{n-k}=M_n\},$$ the time elapsed since the process $(X_n)_{n\geqslant0}$ last hit its current maximum $M_n$. Then, due to the symmetry of the increments of the random walk, $\mathrm P(M_{n+1}=M_n+1\,\mid\,\mathcal M_n)=u(T_n)$, where $\mathcal M_n=\sigma(M_k\,;\,0\leqslant k\leqslant n)$ and, for every $k\geqslant0$, $u(k)=\frac12\mathrm P(X_k=0)$. Thus, $u(2k-1)=0$ and $u(2k)=\frac12{2k\choose k}2^{-2k}$ for every $k\geqslant1$, hence the sequence $(u(2k))_{k\geqslant1}$ is decreasing. Since, for every $0\leqslant k\leqslant n$, $[T_n\geqslant k]=[M_{n-k}=M_n]$, this shows that the conditional probability that $[M_{n+1}=M_n+1]$ depends on the past in a possibly unlimited way.
1.2 The analogous continuous time process is the standard Brownian motion $(B_t)_{t\geqslant0}$. Consider $S_t=\sup\{B_s\,;\,0\leqslant s\leqslant t\}$. Then $(B_t)_{t\geqslant0}$ is a Markov process but $(S_t)_{t\geqslant0}$ is not.
2. Other examples without the Markov property are the processes of local times.
2.1 In the discrete setting, consider $$Z_n=\sum\limits_{k=1}^{n}[X_{2k}=0].$$ Then $Z_{n+1}$ is either $Z_n$ or $Z_n+1$, and the probability that $Z_{n+1}=Z_n+1$ depends on $$\max\{0\leqslant k\leqslant n\,;\,X_{2n-2k}=0\},$$ the time elapsed since the last zero of the random walk. For reasons similar to the ones explained for the maxima processes:
The process $(Z_n)_{n\geqslant0}$ is not a Markov process, nor a Markov process of any higher order.
2.2 The analogous process for the standard Brownian motion $(B_t)_{t\geqslant0}$ is the so-called local time at zero $(L_t)_{t\geqslant0}$. Likewise, $(L_t)_{t\geqslant0}$ is not a Markov process.