It should be noted that according to the view of the Noda B'Yehuda, someone who is found on a distant journey (from Modi'in and outward) is not commanded to bring himself near, and is exempt from the offering. If so, the whole question does not exist, because we are not talking about hundreds of thousands of people, not even tens of thousands of people, and not even thousands of registered groups.

The pilgrims are in Jerusalem.

Historically, it is fairly clear that the Jewish community of Rome did not make pilgrimage three times a year—a journey that took several months in each direction and involved no small amount of danger. It is also not likely that all the males in the Babylonian Jewish community invested several whole months every year in pilgrimage (even though they were waiting for them before beginning the prayer for rain), nor the closer community of Alexandria. Even within the Land of Israel, a journey of several days each way from Dan to Beersheba three times a year is not likely to have taken place in a sweeping and universal way.
Apparently, for the Passover offering they were considered to be on a distant journey and there was no obligation to bring oneself near; and regarding pilgrimage, from a certain distance they were considered altogether like "one who is exceedingly delicate and cannot go up on foot," who is exempt (or according to the view of the medieval authorities (Rishonim) that one who lives outside the Land is exempt), or they exempted themselves because of the danger of bandits on the roads. And those who did arrive on a regular, consistent basis were the people from nearby places and a minority of especially pious individuals.

First, I would have expected one of the answers here to be that it is not at all certain that this is what actually happened.

Second, I share the desire to understand the Mishnah and the Talmud. But it is always hard for me to understand why you assume from the outset that you can understand those who came before you. Why do you relate to them as your equals?
The stature of a person and the human strength that you know today are completely different from what existed in the time of the Hebrew Bible (Tanakh), the Mishnah, and the Talmud. The priests were stronger and very swift, and indeed could carry out the task. Whether it was hard or easy—we also cannot know.