And seeing what happened in that battle, Mega-Khan should. Be. Banned.
I believe one battle is not enough to decide whether or not a Pokemon should be banned. I've played one battle of Megamons as well, where I had a narrow victory, mostly because my team matched up well against his, and even though I was using Mega Kangaskhan, I was nowhere close to getting a 6-0 sweep.
That set you posted is strong, but has a hard counter: Any ghost with a support move such as Toxic, Will-o-Wisp, or Trick. This makes it a toss up whether or not to run Sucker Punch over say, Crunch. Without Sucker Punch the set gets hurt by powerful, fast Fighting mons, notably:
252+ Atk Adaptability Mega Lucario Close Combat vs. 252 HP / 0 Def Mega Kangaskhan: 624-736 (150.7 - 177.7%) -- guaranteed OHKO
252 SpA Fist Plate Arceus-Fighting Judgment vs. 252 HP / 0 SpD Mega Kangaskhan: 372-438 (89.8 - 105.7%) -- 37.5% chance to OHKO
Also, Sableye could be switched in to take Parental Bond Crunch and proceed to burn the Kanga or Trick it a Scarf, then spam Recover.
252+ Atk Parental Bond Mega Kangaskhan Crunch vs. 252 HP / 252 Def Sableye: 133-157 (43.7 - 51.6%) -- 9% chance to 2HKO
Another solid Pokemon that can take some punishment is Mega-Scizor. If Kanga has already used Power-Up Punch, Mega-Scizor could be sent out to revenge, and survive a +2 Sucker Punch and hit back hard.
+2 252+ Atk Parental Bond Mega Kangaskhan Sucker Punch vs. 252 HP / 0 Def Mega Scizor: 208-246 (60.4 - 71.5%) -- guaranteed 2HKO
252+ Atk Mega Scizor Superpower vs. 252 HP / 0 Def Mega Kangaskhan: 320-378 (77.2 - 91.3%) -- guaranteed 2HKO
I don't have much play time but I think that more testing on Mega-Kanga should be done.
But even so, it meant he'd look like a fool using a Pokemon like that who has the sole purpose of destroying anything because it is capable of doing that.
Anyways, there are counters, but as always, you can't always keep a Ghost- or fast Fighting type which can OHKO it (M-Luke) just to counter it! That definitely means it's not good for the tier.
A Pokemon that can destroy anything shouldn't have counters, and every team could have a ghost if that's what the meta becomes. I play Balanced Hackmons mostly and Giratina is on roughly 1/3 to 1/2 of the teams I battle.