The fastest way that is least time consuming is to just use extremely levelled characters. Baal is only level 4000, after all.
Of course, you don't have such right now. So to do this in the quickest fashion will probably involve just getting bigger and badder dragons until you get the biggest and baddest dragons. You have some at level 4500, and you have access to the Beauty Palace stage which has big dragons. Provided you weaken the target a bit, it's possible to capture a stronger dragon with a weaker dragon. I've never personally tried this strategy, so I don't remember the general threshold that you should be shooting for - I seem to recall it being around 500-1000 levels higher as being safe.
So, using a combination of Stronger Enemy bills and throwing dragons into each other, capture progressively badder dragons until you eventually capture a level 9999 dragon. Consequently, use it to capture 9 more. With 10 level 9999 dragons. and good equipment (even if not leveled completely through the Item World), you should be able to take down a level 4000 Baal without too much problem. Don't forget to pass the Weaker Enemy bills to drop his level back down.
Of course, you probably don't need to go all the way to 10 level 9999 dragons. . You could probably accomplish it at a lower level and with possibly fewer dragons, but if you want a mostly guaranteed victory, this is about the way to do it. It may take some doing to handle the right threshold for capturing, but the time spent figuring that is shorter than how long you'd spend building up characters normally.