Thing about Paper Mario is that Nintendo fully owns him, no questions asked, full stop. He's been around since 2001 and has the potential to be a full, unique fighter, especially after Thousand Year Door... but they haven't bothered putting him in yet. It's a bold statement for me to make, but Paper Mario seems to be in an honest-to-God "if they wanted him in, he would be in by now" situation - there would have been no reason to not add him to Brawl or Smash 4, or even as DLC in Smash 4 if they really felt the need to shill Color Splash or try to boost interest in Sticker Star, and the same goes for Ultimate's base roster, or even as a shill in Byleth's place that would have been much better accepted.
...So when was Nintendo choosing the DLC outside of a little of Smash 4(Corrin and maybe Bayonetta) and this game?
There wasn't "multiple chances" in that regard. Sakurai was the one choosing the characters. This is the first set of DLC where Nintendo is incharge of who is getting in(and arguably a little of Smash 4). They didn't choose the base Ultimate roster either.
So I don't see how this really matters.
-------------------
I forgot to comment on the PP part.
We don't know if it was ever base. That's an assumption based mainly upon conjecture. The Palutena's Guidance could've been a late thing, during PP's work, but well before Joker started work on. PP is fairly unique, and we found data at least 6 months beforehand. It's very easy, once it was decided to be DLC(whether it was base or not at any point doesn't change this factor), to have the voices done for that. The recordings could've been done during any time during that 3 year span, so it doesn't give us any real information on what to expect. Also keep in mind the DLC wasn't finalized till November 2019. Sakurai wouldn't have given only half the DLC messages, so only PP got its own anyway.
I've heard the Classic Mode thing with Greninja, and it's not really convincing. Yes, it's strange there's only one Grass guy, but they didn't throw in Pikmin & Olimar either, or anyone who barely resembles plants like Peach either. The idea they changed it and removed PP doesn't hold much water, since it would've been just as easy to change it to add more but remove PP. It goes both ways.
The amiibo is newer one brought up, but it actually shows it was meant as DLC as is at that point. The character's amiibo is listed after all the other characters, including Richter, and right before Joker. Whatever was decided was based upon a DLC factor at that point. It coming out early doesn't mean much. Not all amiibo take the same time to make, not with licensing factors involved.
The missing data, which is within the list of newcomers, is the only thing remotely leading to it, and it clashes heavily with the amiibo's listing too. Both are listed differently. It may not have been PP data. It could be scrapped data like a Proof of Concept for Hero, which is odd to be in the game, but that's why it was removed. Do note I don't think it was likely Hero. But it wasn't definitely PP either.
There's nothing really for Spirits that's legitimate evidence either. None of the spirits are missing/removed for PP. And any Plant could evolve into Petey Piranha, nor are half all Spirits super logical or doing perfect research. Masked Man had the wrong sprite, fanart. I doubt they cared that much who could evolve into Petey at that point. It's a Plant. Besides that, Petey is summoned by PP as a Final Smash, so they weren't even treated as close to related either way. A lot of the evolutions work fine, but there's some details that are strange and don't work anyway. Realistically, Petey would've been separate and not evolve from Nipper Plant if it was that important that regular Piranha Plant was involved. It doesn't really imply some kind of spirit switch. It's more "Sakurai's crew chose it and made it work in a fun way that isn't perfectly logical". In fact, the Absolute Safety Capsule is perhaps the funniest one of all. It's the empty version, but considering they didn't even know who was Masked Man's correct sprite, they probably were treating that as a joke to represent Porky as is, not to say "he's missing". They're error prone. There's also no real evidence Sakurai removed any spirits either from the final one, as that was just something that people thought was the case(though to be fair, I misread it to be the case too, so some of that was from me). Obviously some did have to be removed for licensing issues, but that's kind of it. But otherwise, there's no real reason to believe we had a PP spirit removed from the total either because of DLC.
So basically, only the "missing data" is legitimate evidence, and being characters were worked on in different orders, not based upon reveal order specifically, We don't know enough of the development period where the missing data is relevant either. It might've been a placeholder while PP was being figured out. It doesn't necessarily mean it was ever intended for base. There's extremely loose information at this point even with that data in mind.