You can always just add the Part <$R> bit to the title prefix, as you normally would. That’s what I did when I created a Pandoc ebook format a while back. Title prefixes change the text of the title, so anywhere that title would be printed (such as the ToC), that is how it would appear. Markdown has no formalisation of “Parts” and “Chapters” because these constructs are mostly cosmetic when you think about it. They vary in how they are presented (pure formatting) and how we talk about them (text), but other than that there is no such thing as a “chapter” in the ePub specification. Scrivener doesn’t have these things either, it’s all just words used to describe things.
As for the formatting of the ToC itself, while these instructions are for Scrivener’s generator, the basic concept applies since both Pandoc and Scrivener generate a standard navigation table. You should be able to copy that CSS and tweak it how you want it to look. The main difference is that it would be placed into the Pandoc Options compile format pane, rather than a dedicated CSS pane, in the Format Designer window.
One thing to be aware of though is that when you leave the CSS blank (as it is by default, for this very reason), Pandoc generates some prefab styling for the ebook. So for the most consistent results you would want to open up the .epub in an ePub editor and copy and paste the prefab CSS into your compile settings, and then add whatever additional CSS you want for the ToC.
Of course if you do not want any of that and wish to design it yourself from the ground up, you can skip the step of copying the prefab CSS out of Sigil or whatever. I do mean ground up though—an ebook without any CSS is going to look very vanilla.