Janeway thing is easy for me to justify. It seems, based on what we've seen, Starfleet ships (or their crews) are lost all the time, often from strange space phenomena, and what happened to them isn't discovered for years or decades later. From Essex in the 22nd century, to ships like Discovery, Bozeman, Hera, Equinox, and of course Voyager itself, etc., the idea of space as a dangerous place where ships can just disappear, or be destroyed by random encounters with phenomena or hostile aliens would be with no explanation for a long time, if not ever, must be a pretty common thought.
Think about how, in 2374, at the time of the greatest threat to the existence of the Federation outside of the Borg, when the casualties were mounting, and the enemy seemed to be capable of generating new forces at a whim, and a core Federation world falls to this enemy (Betazed), morale would be very low, not only in Starfleet, but in the Federation at large. People would be desperate for a sign of hope.
Then you hear about how, one ship, thought lost three years ago, and whose crew were declared legally dead only months ago, turns up alive and making their way back. They're unthinkably distant, but the crew is mostly intact, and somehow they are not only more than 10,000 light years closer to home than they were first stranded, but have found a way to communicate with home, even if only temporarily. Even if it was classified (the circumstances about Prometheus would probably be, especially since the Romulans, potential allies in the Dominion War, were involved), the crew received letters from home, so the families of those who were missing, knew, and I would imagine keeping that secret would be near impossible. We know that it was an open secret by the time of "Author, Author".
As the news spreads, a lost ship surviving, questions about its survival would crop up. Knowledge would spread that Voyager's crew had expanded, absorbing a Maquis crew, natives to the region, and even liberating Borg! Voyager, despite being in the most horrible situation, where they must be constantly on edge, with no refuels or personnel replacements, was bringing the idealism of the Federation to the distant Delta Quadrant while also single-handedly fighting off Borg ships (after two battles with Borg destroyed dozens of ships before). It would be astounding to conceive of, and a beacon of hope.
And who led this amazing team of heroes that have survived so far away? Captain Kathryn Janeway. The name Janeway would be synonymous with leadership in times of crisis. "Can we survive this war?" "If Captain Janeway can keep her ship and crew alive and thriving with little more than the spirit of Starfleet and the Federation as a resource, you know we can!"
And then, three years later, Janeway brings her crew home. Mostly alive. Voyager intact. Two former Borg aboard. Only seven years after being lost 70,000 light years away. Who would get the credit? Sure, the ship's crew, but its leader would be the focal point of that fame. Captain Kathryn Janeway.
So, three years ago from the Lower Decks perspective, Janeway the amazing Starfleet hero, completed her monumental task, and members of her crew, like Tom Paris, are used to boost morale in general. Now think of how rumor would spread this idea and distort it among the local populations. Klingons, Romulans, Ferengi, Gorn, etc. Eventually getting into the ears of the Pakleds. Are they truly as stupid as they seem? I dunno, but if they are, I can easily see them confusing the legendary Janeway for any female captain, much like they confuse any singular Starfleet ship for Enterprise.
