In the last slot Substitute is best overall, making Medicham completely terrifying to deal with thereafter, followed by BP (Medi can actually run Sub+BP with just STABS very effectively finding times to pass easily thanks to its forced switches and gives safe entrance to things that can handle Aegislash etc). Ice Punch is mandatory if running coverage, Fire Punch is useful to snipe or safety against Protect Ferro but TBH you're best off double switching or BPing and letting teammates trap/handle Aegislash. Fake Out is niche, yes, but is extremely viable, giving Medicham much more use against the HO teams it normally struggles with. Now that Deo is gone Medi has a niche in beating the vast majority of HO leads -- Fake Out lets it break the sash and avoid the speed tie with Mamo and Breloom, disallowing even SR to go up, kills Terrak after taking a hit or SR going up, and if you really wanna go anti-lead 20 HP EVs guarantees it doesn't get OHKO'd by Garchomp's Outrage, letting you kill it off with Ice Punch. It has a couple more emergency uses, ie picking off REALLY weakened HO mons, scouting Zards, guaranteeing the 1v1 with all Dragonite.
Ultimately the move does not play to Medicham's strengths all that well, but allowing it to adjust its role to anti-lead against teams where its matchup is usually poor has good value.
Also, although the power difference seems small, Zen Headbutt is important for netting certain O/2HKOs and the flinch odds compound your chance of beating certain would-be checks behind a Sub. For example, it always 2HKOs Clefable after SR (most important), always OHKOs offensive and SpDef Venusaur, always 2HKOs Gyarados at -1 (!_!), and is generally a surprisingly great spam move since unlike with Psycho Cut its power is actually notably better than a resisted HJK lol. Psycho Cut isn't a bad choice at all imo, but the extra BP of Zen Headbutt plays best to Mega Medicham's strengths -- he is not a timid wallbreaker.