There is no evidence that Paul was a mentat, but rather he had some mentat training from Thufir Hawat.
Reverend Mother Mohaim indicates to Paul during Chapter 1 that the Spacing Guild emphasizes almost Pure Mathematics:
She nodded. "We have two chief survivors of those ancient schools: the Bene Gesserit and the Spacing Guild. The Guild, so we think, emphasizes almost pure mathematics. Bene Gesserit performs another function."
This is math training different from being a 'mentat'. However, it would stand to reason that this training is related to the actual navigation of the ships through fold space.
A second part of navigation is the spice-based prescience which allows prediction of the paths ahead. Paul, being Kwiswatz Haderach, could see the paths ahead, and thus has half of this combination. However, lacking the pure mathematics training, it is unlikely he could navigate a ship until he actually got some coaching in the matter.
It is possible that this knowledge might be present in 'other memories', but this also seems unlikely since that would require a Guild navigator (or adept, at least) have previously been part of the Bene Gesserit breeding program in lineal antecendence to Paul. Given the paragraph quoted above, combined with the general sense of xenophobic both organizations exhibit, this also seems unlikely.
While not explicitly addressed (and likely such a task would be beneath the emperor anyhows), it seems unlikely Paul could actually navigate a Guild vessel.