Paul will never be able to use Mega evolution for one simple reason. Mega Evolution requires trainer and Pokémon to have a strong bond. Even Korrina and Lucario struggled with and they were portrayed as close from the start, Paul's Pokémon either hated him or were given no reason to like him. Paul was callous and even cruel towards them using them only for his personal glorification. In many ways he's the most evil character in the main anime (movies excepted), except perhaps Hunter J, Giovanni and maybe Lysander. It is cannon, in the anime that friendship is the way to make Pokémon stronger and on that basis Alain would probably win. It's odd that the fandom seems to have such a draw to Paul despite being the worst handled rival of all - a sociopath with the same level of cruelty as any villain yet he receives no justice for his crimes.
I can see why Paul's bond with his Pokemon would seem like an issue. I also greatly dislike how he treated Pokemon like Chimchar. But how cold he initially was made the warmth he gradually gained throughout the Sinnoh Arc that much more compelling. But first, regarding the Korrina situation, the problem with them is that they were so close they took each other's input for granted. Lucario as a species was also implied to be subject to specific elements of its Mega Evolution - its Aura becomes completely maxed out. And since Lucario as a species regularly uses Aura to read the emotions of others and enhance their ability to sense their environment, etc., an inability to control one's Aura directly interferes with Lucario's ability to process lots of input from its environment. This was illustrated when it was only able to process information regarding its opponent - everything else was dulled.
Paul was certainly a harsh trainer, but his "cruel' training tactics were ever only seen applied to Chimchar. During the episode "Turtwig, Grotle... and Torterra!" (I can't remember the Dub Title), we even saw that Paul had arranged for his Pokemon to be looked after as they relaxed. Even when Torterra went out of his way to help out Grotle despite not having to, Paul just said he did something unnecessary, despite the fact Torterra was helping Paul's immediate competition. We gradually see Paul's treatment of his Pokemon grow more outwardly positive as the series goes on - he even reassures Electivire after it loses to Infernape in the Sinnoh League. And while he claims Aggron and Gastrodon "agreed to go down", it's unlikely they never intended to win. They likely just battled more Defensively than they otherwise would have (with Aggron using Metal Sound, and potentially wearing out Infernape with recoil from Flare Blitz, coupled with Gastrodon's Muddy Water Counter Shield).
And Mega Evolution in the anime, while appearing to require more than in the games, doesn't necessarily require an immense "bond" per se. We see in the episode where Team Rocket tried to forcibly Mega Evolve Garchomp that all that's really required from the Pokemon is their consent. A Pokemon can actively resist Mega Evolving if they don't consent to it, but otherwise just having the Keystone and Mega Stone seems sufficient. The only transformation that has been shown to require an extremely close bond is Ash-Greninja's Bond Phenomenon. Odds are Paul, by the end of the Sinnoh League, would definitely be able to use Mega Evolution if he acquired a Pokemon capable of using it.
Strategy won't come out on top all the time. Ash is a strategic battler too, but even with using his best Pokémon with the best strategies he can be defeated - He had the strategy of using the masts on Drake's ship in AG to help Grovyle battle Altaria but still lost that battle terribly to the stronger trainer. Cameron's Samurott had a strategy to deal with electric type moves by using it's seamitar to block the attacks - it still fell to Pikachu. If there isn't a comparable level of strength between the two Pokémon or one Pokémon has a major disadvantage it may not be possible to create a strategy that can allow for the disadvantaged or weaker Pokémon to succeed.
That's true, but it's worth keeping in mind that Ash had only just begun to think strategically again towards the end of that battle, after having an overconfidence streak beforehand. Not to mention Grovyle wasn't fully evolved, and Altaria had a quadruple resistance to his main attacks. And that's all before factoring in that Altaria's trainer was an Elite Four member. And I'd argue BW's battles aren't a great indication of how strategies would be overcome, but even in the case you mentioned Cameron was never written as a terribly intelligent trainer, so it's pretty believable that any strategies he would employ wouldn't be terribly effective.
He beat Ash because his Pokémon were stronger than Ash's. They probably were at the time he faced Cynthia too. That doesn't itself denote there had been an improvement. In any case the fact he lost to Ash at the league indicates he wasn't improving with the passage of time.
Paul was training far more Pokemon than Ash was throughout Sinnoh. Ash just focused on his single team of six and used reserves for early rounds of the League. The only Pokemon you could argue lost even with fair "improvement" is Electivire, and even then he was able to withstand several of Infernape's attacks even while Blaze was activated, something even Volkner's Luxray had trouble with. We also know for a fact that Drapion, who was shown to be immensely powerful, was caught a while after he released Chimchar. So I'd argue Paul showed tremendous improvement as far as his Pokemon's stength is concerned, particularly given how many Pokemon he was training at once. Many feel that had Paul just used more Pokemon he had already put more training into against Ash (like Torterra, for instance), Ash's Sinnoh Team never would have won.
It wasn't clear that he improved from the Cynthia battle at all. Paul stayed more or less at the same level throughout the DP series loosing as badly to Brandon as he did to Cynthia and eventually falling to Ash, who had spent the entire series improving. It's also worth noting here that Alain has held his own against both champion Steven and Seibold of the elite four. He even beat Malva after fighting 9 other mega evolution trainers previously, although I'd still dispute whether that fight was legitimate, and he managed to get all 8 Kalos badges in remarkably short period of time. All of that suggests in terms of strength he's a cut above Paul.
Well, Paul did use a team of unevolved Pokemon against Cynthia, barring Torterra. And several of them evolved over the course of the saga (such as Murkrow). So based on his Pokemon choice alone most of his subsequent battles did involve him in being in much better form. Brandon used Regirock, Registeel and Regice when just using one of them on a normal team is generally enough to make him the strongest Frontier Brain in Kanto. I'd argue their strength at the time was beyond that of a typical Elite Four member's (at the very least beyond that of members like Aaron), especially given they all took Super-Effective damage from Regigigas at point-blank range, whose strength is comparable to Kyogre and Groudon. Alain's Charizard after Mega Evolution was OHKO'd by Groudon post-Primal Reversion. So the implication is that Brandon would probably give Alain trouble as well. And suggesting Ash won against him as a counterpoint isn't quite valid, since Ash won against him while Brandon was using a Regice after just catching it. The only clear measure of Ash's strength compared to Brandon's was Sceptile VS Regirock, since he had Regirock long before the others. Even with a type advantage and underhanded tactics Ash still lost.
Regarding Alain battling Siebold and Steven, he just didn't immediately lose against either of them. We've never seen Paul battle against an Elite Four member, but there is likely a bit of variation in their strength. Elite Four Aaron's Pokemon took noticeable damage even from Team Rocket's attacks, whereas Flint's Infernape alone was able to KO two of Cynthia's Pokemon and nearly KO Garchomp afterwards. So we can't know for sure where Siebold stands amongst the other Elite Four. But in either case, he's weaker than Cynthia. Charizard taking the initial Dragon Pulse was very impressive. But we can't know for sure how much stronger Cynthia is than Siebold, and by extension Alain. Yes, managing to take attacks from Steven's Mega Metagross is also impressive, but both Flash Cannon and Meteor Mash were resisted (and the former didn't get a Tough Claws boost, either). And Metagross didn't seem to take any damage from Blast Burn - the same move that KO'd Malva's Mega Houndoom through its resistance. So the implication is that Champions are much stronger than Elite Four members, one of whom Alain managed to defeat. Torterra is probably near Elite Four level, given Ashs Torterra could already hold his own against Bertha's ace Pokemon, and Paul's had his for MUCH longer.