Mechanically, by RAW, he would be locked into his original class of Fighter, so this would be:
1. Spending feats to multiclass into whichever divine class he wants to pursue.
. A. Typically four feats, one for the original multiclassing, then one each for Encounter, Utility, and Daily power.
2. Either:
. A. Taking a divine-flavored Paragon Path (unlocked by his Multiclass) or
. B. Using Paragon multiclassing to take additional Prayers / powers from his second class.
He can wind up with 7 powers from his second class for a cost of four feats plus his Paragon path.
Alternately, he can roll up a new character, retire the fighter, etc.
Anything else you let him do should result from a negotiation between you and the player; in particular I'd stress that any form of "complete rebuild" is a one-off, not something he can expect to do several times over his career.
I'd probably also push him to build a version of his priest that closely matches his available Fighter powers (for minimal ret-con): e.g., spending feats if necessary to become proficient in his original armor, weapons, etc., possibly even multiclassing *the other way*, e.g., spending a couple multiclass feats on Fighter powers, etc. Remind him that he can "retrain" these feats later on, one per level gained, towards a more optimized version of his new class.