Sure, Markov's principle matters for some things, but it seems to me Markov's principle doesn't really matter for this particular claim ("for every prime p, such-and-such a decidable property phi(p) is true"), since the only unbounded quantifier is the initial universal one. Any classical proof of a Pi_1 (or even Pi_2, using the Friedman translation) proposition can be straightforwardly turned into an intuitionistic proof of the same proposition (technically, I mean specifically that Peano Arithmetic is Pi_2-conservative over Heyting Arithmetic [and I suppose there are similar results for stronger systems but we don't need those]).
So there is no surprise that this particular statement's proof is constructive, given that it is classically provable at all [again, technically, I am referring to classical provability in PA, but it would be shocking if Fermat's old proof, or any other anyone bothered with for a statement of this sort, had somehow relied on anything beyond PA]. For other more quantifier-complex classical theorems, it would be of more note to observe whether a particular proof could be made constructive (in the mere sense of intuitionistic mathematics) or not, but for this one, there's nothing to it.
Anyway, I think I'm arguing pedantically about something there's no reason for me to argue about at all. Sorry about that! I think we're both in agreement that this is great, its constructiveness is great, math is great. Hooray!