Really the DM ought to toss out names, reacting to the actions of the party, and just see what sticks.
My NPC’s will start recognizing the party by their recent exploits, such as “The Heroes of Phandelver” — or “The Butchers of Phandalin,” as the case may be.
If the players want to “rebrand” the party, that’s just another quest goal. Always attainable, but you can’t murder-hobo your way to being beloved by the countryfolk.
One PC I play is one of “The Orange Cart Heroes” (the DM’s invention) after a minor but very public encounter. That’s fun. It doesn’t matter that our later exploits ought to be more noteworthy.
The meme is right: Asking the players to name their team typically ends up like the end of Mystery Men where every idea is worse than the last. The good idea comes from the journalist talking to them.