Here's how I did this and what you will need.
(1) Access to Paine's Bushido, and Cactling Gun and Rikku's Armor Eraser in the Mascot DSP. Access to Paine's Nonpareil in the Samurai Dressphere.
(2) The Higher Power GG (gotten from the Ruin Depths aka the Amazing Chocobo dungeon) or the Invincible accessory (you can get one from Youth League base in Kilika if you used the binoculars every chapter) for Paine. This is absolutely necessary to Break Damage Limit.
3) 1-2 Kaiser Knuckles or the next best +Strength accessory you have. If you're using Invincible, the Pride of the Sword GG will be used for maximum +Strength. You can also use Blood of the Beast, Samurai's Honor or Flash of Steel, but Pride of the Sword is the most commonly obtained in a given playthrough.
Whether Paine has Higher Power + 2 Kaiser Knuckles or Pride of the Sword/Invincible/Kaiser Knuckles, by going through all the GG gates in battle you will get Break Damage Limit and +120 Strength. This means that by level 68 in the Mascot DSP, Paine will reach the maximum Strength of 255. I do not know if 255 is strictly necessary to deal 99999 damage, it may work lower than that.
Then, simply Armor Eraser a weak enemy three times (Low floors in the Via Infinito or weak teams in the Battle Simulator will do. I used the Coyote from the Impressions team.) and use Nonpareil five times on Paine, then finally use Cactling Gun.