When did it happen relatively to his reign in Sanhedrin?
It seems that it happened fairly in the beginning of his time in the Sanhedrin, as it's stated that one of the sages that escaped at the time was Yehoshua ben Perachiah, who was of course part of the zug that preceded Shimon ben Shetach and Rabbi Yehuda ben Tabbai (Sanhedrin 107b):
"What is the incident involving Yehoshua ben Peraḥya? The Gemara relates: When King Yannai was killing the Sages, Yehoshua ben Peraḥya and Jesus, his student, went to Alexandria of Egypt. When there was peace between King Yannai and the Sages, Shimon ben Shataḥ sent a message to Yehoshua ben Peraḥya: From me, Jerusalem, the holy city, to you, Alexandria of Egypt: My sister, my husband is located among you and I sit desolate. The head of the Sages of Israel is out of the country and Jerusalem requires his return."
If Yehoshua ben Perachiah was still alive at the time, it seems that Rabbi Shimon was still fairly new in the Sanhedrin.1
Is "כל חכמי ישראל" metaphorical or literal?
It's definitely metaphorical. We know this because the gemara records other sages who managed to escape Yannai's wrath. The source about Yehoshua ben Perachiah was brought above. Together with him, his student Yeshu survived. Like it or not, this Yeshu started out as a talmid chacham. Yehuda ben Tabbai also survived (Yerushalmi Chagigah 11a, my translation):
"Yehuda ben Tabbai...escaped to Alexandria and the people of Jerusalem wrote to him: From me, Jerusalem, the holy city, to you, Alexandria of Egypt: My sister, my husband is located among you and I sit desolate."
Though the Yerushalmi doesn't state when this story happened, as this is the same letter that was sent to Yehoshua ben Perachiah, this happened most likely in the same time (and so writes Avraham Korman in "Sects and Cults in Judaism", pg. 234, footnote 28, although Rabbi Aharon Heiman disagreed with this conclusion).
And since we find that three of the biggest sages at the time managed to escape, it is very likely that some of the lesser-known ones managed as well (such as Yeshu, student of Yehoshua ben Perachiah).
It's also possible that Choni Ha'Me'agel was already active at the time. Though Shimon ben Shetach was evidently already one of the heads of the Sanhedrin (as opposed to a "regular" member) when Choni prayed for rain, as the power of excommunication was in his hands, Rambam in his Introduction to the Mishna mentions Choni together with the group of Shimon ben Shetach and Yehuda ben Tabbai, which makes it sound like Choni was not a student of the rabbis of Shimon's generation but of those of the previous generation. Moreover, the respect he receives in that story hints to him having already been well-known, a status usually found by an older sage. Rambam also mentions Rabbi Elyehoeinei ben Hakof in that group, so he may have already been active at that time as well.
Rabbi Yehoshua ben Gamla was probably also active at the time as well. As Avraham Korman in his book "Sects and Cults in Judaism", pg. 233-234 and footnote 28 there, wrote (my translation):
"How did Shimon ben Shetach manage to restore the Torah to its former glory? There are hints to that in aggadot Chazal. [Footnote:] The turning of the young children away from their faith pushed Shimon ben Shetach to organize a network of schools to teach Torah from a young age. He was successful in this task thanks to assistance from the High Priest Yehoshua ben Gamla, who was also very wealthy (see Bava Batra 21). He was also mentioned in Yevamot (61) where it is told that his wife managed to secure the role of High Priest for him, by giving a large amount of money to King Yannai. See the Rashash Bava Batra there, who says that that which is said here that Yehoshua ben Gamla established teachers of children in every city and if it were not for him, Torah would have been forgotten from Yisrael, that it is said in the Yerushalmi (the end of the eighth chapter of Ketubot) that Shimon ben Shetach was the one who did that. It seems that they helped one another until they were successful."
It should be noted that this understanding of the story of Rabbi Yehoshua ben Gamla does not line up with other sources about him and his wife, Marta bat Baitos, so some suggest that there were two Rabbi Yehoshua ben Gamla (see Tosfot Yeshanim on Yevamot 61a).
Lastly, Shimon ben Shetach replaced all Sadducean members of the Sanhedrin with Pharisaic sages (Megillat Taanit, 28th of Tevet), so there were likely enough sages still alive to be able to join the Sanhedrin.
What did the "restoration" include?
The restoration included a number of things:
He instituted, apparently with the assistance of Rabbi Yehoshua ben Gamla, a "mandatory education law" (see above). This was necessary in order to weaken the Sadducean hold upon the younger generations.2
He managed to remove the Sadducees from the Sanhedrin and return the halachic reigns to the Pharisees. This was achieved thanks to the fact that most of the nation followed the Pharisaic teachings, so even when the Sanhedrin was turned over to the Sadducees, they acted as though they were Pharisees, otherwise no one would follow them (Korman, pg. 235, footnote 34, per Josephus, Antiquities 18:1:4). When his sister got him pardoned (and similarly here too), he joined the Sanhedrin. From this position he was gradually able to prove that each of the Sadducean judges was unfit for the role of being on the Sanhedrin, which allowed him to get them fired (described in Megillat Taanit, 28th of Tevet and in aggadic fashion in Sanhedrin 19) and return the Sanhedrin to Pharisaic hands (the day this task was completed was recorded as a day of festivities in Megillat Taanit).
He probably had a hand in influencing Yannai's return to Pharaseeism at the end of his life (Sotah 22b), thus returning the royal family to its halachic roots.
How did he replace all other rabbis? Did he incorporate other's sources or only his own tradition?
As shown above, it was not necessary to replace all of the rabbis because at least some survived the "Pharisaic genocide". In fact, he wasn't really "restoring" all of the Oral Torah. What he did was make sure it remained rooted in Am Yisrael. He was restoring the status of the Oral Law to its former legal and judicial glory. For the completion of this important task, he was credited in aggadic fashion as the restorer of all of the Torah. The break mentioned by Daf Shevui might refer to the knowledge preserved only by sages that were killed in the genocide, which was apparently lost when they were killed. That said, it seems that the vast majority of the knowledge was preserved.
1 Interestingly, this might partially resolve a dispute in Chagigah 16 where it says:
"...The first members of each pair served as Nasi, and their counterparts served as deputy Nasi. GEMARA: The Sages taught: Three of the first pairs who say not to place hands and two of the last pairs who say to place hands served as Nasi, and their counterparts served as deputy Nasi; this is the statement of Rabbi Meir. And the Rabbis say the opposite: Yehuda ben Tabbai was deputy Nasi and Shimon ben Shataḥ was the Nasi."
Per the story of Yehoshua ben Perachiah, we might say that first Shimon ben Shetach replaced Nitai Ha'Arbeli as head of the court while Yehoshua ben Perachiah was still alive, and when he died, Shimon became the Nasi and Yehuda ben Tabbai became head of the court (and so appears to hint Rabbi Aharon Heiman in "Toldot Tannaim v'Amoraim", pg. 380).
2 According to the Rashbetz (Magen Avot, pg. 193), the first Karaites came into existence during the time of Shimon ben Shetach. Korman, pg. 232 explains that since most of the nation followed Pharisaic teachings, the Sadducees, even when in power, could not teach their hashkafic views. So they taught them Tanach as Sadducees learn Tanach. Thus, the Karaites were born: People possessing the normative hashkafic views of Am Yisrael (such as belief in the Resurrection) but with the Sadducean understanding of Tanach and halacha (a literal, p'shat understanding).