The first answer of the gemara (see above, g:4) was that "he removed the Lechem off the Shulchan before the next erev shabbos and put them back shabbos morning. But then this information should have been the solution when the gemara asked "Keitzad ?".
Mainly: What is the solution for the one who did not replace the lechem on Shabos ? The answer should have been: Put them back on the shulchan but not before next Shabbos morning. "Ikar mechusar min hasefer" !
You are asking an excellent question. Why does the Mishnah (Menachos 90a) say, "What should he do, he should keep it [on the Shulchan] until the next Shabbos...," it should have said, according to Rava, "He should leave it off the table [so that it won't become Kadosh on the evening of Shabbos] and only replace it on the SHulchan the next Shabbos."
Perhaps that is actually the way Rava did read the Mishnah. "Yanichena l'Shabbos ha'Ba'ah" may mean, "he should place it there on the following Shabbos" -- that is, it does not become Pasul when placed on the Shulchan too early unless it is there on the evening of Shabbos.
Alternatively, the Mishnah is not discussing how to avoid future problems of becoming Kadosh Lipasel, but rather it is just teaching that the original act of placing the Lechem on the Shulchan too early does not disqualify it.