I believe the answer should depend on your background, aspirations, whether you want a theoretical or applied reference,
In my opinion, a very good book which basic measure theory and discusses various types stochastic processes such as Markov, Levy and Brownian motion is: E. Cinlar, Probability and stochastics, Springer editions, 2011. It also has exercises in almost every (no pun intended) section. I have found this book particularly helpful and comprehensive and this would be my #1 recommendation.
My second recommendation is a more advanced text which would be suitable for either advanced university students or graduate students. This is: D.A. Levin, Y. Peres and E.L. Wilmer, Markov Chains and Mixing Times, 2009. Although the material this book presents is quite advanced, the presentation is rather comprehensible accompanied by many examples. At the end of every section you can find exercises.
I also very much like the lecture notes of Prof. Oliver Knill, Probability and stochastic processes with applications, Harvard Math. Dept., 2008. These notes are replete of nice examples and exercises. Chapter 3 is devoted to discrete time stochastic processes and only a small part of it focuses on Markovian processes which are treated in a more general context and not as a standalone topic.
A good resource for exercises is the book: D. Gusak, A. Kukush, A. Kulik, Y. Mishura and A. Pilipenko, Theory of stochastic processes with applications to financial mathematics and risk theory, Springer 2010. In Chapter 10, "Markov chains: discrete and continuous time", they give 90 exercises and for lots of them they offer hints. In the whole book, they offer a very concise overview of the pertinent theory followed by a torrent of exercises. Markov chains aside, this book also presents some nice applications of stochastic processes in financial mathematics and features a nice introduction to risk processes.
In case you are more interested in stochastic control, there is an old book, from 1971 by H. Kushner which is considered a standard reference (I've seen it being cited in many papers). The citation is: Kushner, Introduction to stochastic control, Holt, Rinehart and Winston, 1971. It has many exercises and examples and the author focuses mainly on Markov models.
Although you have explicitly asked for a book with lots of exercises, I cannot help not mention: O.L.V. Costa, M.D. Fragoso and R.P. Marques, Discrete-time Markov Jump Linear Systems, Springer 2005. The book offers a rigorous treatment of discrete-time MJLS with lots of interesting and practically relevant results.
Finally, if you are interested in algorithms for simulating or analysing Markov chains, I recommend: Haggstrom, O. Finite Markov Chains and Algorithmic Applications, London mathematical society, 2002. There you can find many applications of Markov chains and lots of exercises.