I've heard various versions of the larger-than-life tale you're referencing (including one in which the antagonist dies simultaneously of stoning, burning, decapitation, and strangulation). Gershon referenced one such version in print, which is translated below.
As to the Shavuot connection, Akdamut is about the greatness of G-d and the heavenly spheres; it then goes into how the Jews were chosen and given the Torah (which is its triumphant concluding line). At the simplest level, it connects as it's about giving the Torah. Gershon's source cites others who point out that the Haftorah of Shavuot is Ezekiel's heavenly visions of chariots, thus Akdamut also spends a while on such imagery (occasionally using wordage from the Haftorah, translated into Aramaic.)
There are other Shavuot connections given, but that's beyond the scope of this question.
Here's the story as found in Gershon's link:
There was once a place where Jews, the offspring of Moses, resided, beyond the Sambatyon river, in peace and tranquility; the local king was a good man and fair to them. But this was a place that valued witchcraft; and a heathen priest arose who, via his witchcraft, could glance at someone with the evil eye and kill them on the spot. This priest began killing many Jews such, and eventually the Jews complained to the king (without whose permission they were powerless to stop this menace). The priest craftily explained to the king that he sought a theological debate with the Jews, and that they must choose a champion to face him; such a Jewish champion would have to be great enough to withstand the sorcerer priest's evil eye. Should the Jew win, the sorcerer priest would be put to death; should the reverse happen, G-d forbid, the king would do away with the Jews. The king gave the Jews three months to select their champion, sending the Jews into deep woe and mourning as they lacked such an individual.
Now the Sambatyon river would rest from noon on Fridays until dusk on Saturday, but it was a ten-mile width; anyone beginning crossing on Friday afternoon would not arrive till the Sabbath, thus violating the Sabbath by walking far beyond the city limits. But Sabbath violation was needed to save this community; however, whoever would arrive there would not be allowed to return as there would be no more emergency dispensation. (Though the Talmud allows emergency responders to return home, this permits the 1-mile rabbinic limit, not the 10-mile Biblical limit). Such a champion, forced to live out his days on this side of the Sambatyon, would have to take a wife from the local, highly-pedigreed Jewish population, and thus must possess outstanding ancestry himself.
Rabbi Meir the son of Isaac, the cantor and great scholar known to us as the author of Akdamut, was chosen; he had a wife and daughter, but faced with no other choice, he divorced his wife so she could have her own life as he would never return across the Sambatyon. Rabbi Meir began his journey on Friday afternoon and arrived on the Sabbath, whereupon he was immediately arrested for his violation. Rabbi Meir then produced his paperwork showing his credentials to rescue the local Jews from their dire straits, and was released.
[Translator's comment - I guess it had to be a local Jew who would be at the debate, but Rabbi Meir gave his wisdom or power to him? The story's unclear about this point.]
Now the debate was to take place on the other side of the Sambatyon; a lottery was conducted and the tailor was chosen to cross the Sambatyon, never to return. He divorced his wife and it was agreed that he should marry Rabbi Meir's daughter. Over the course of the week, the Divine spirit rested upon Rabbi Meir, and he composed the Akdamut liturgy; either it was shortly before Shavuot, or that was the liturgical occasion he was up to in his private study; he gave Akdamut to his son-in-law the tailor and asked that all Jewish communities say it on Shavuot, so that Rabbi Meir would not be forgotten.
The tailor arrived at the debate and climbed onto the stage before the crowd; the sorcerer cast his evil eye upon him, but to no effect. The sorcerer then said to the king, "some amusement before the debate, your Majesty"; he took two nearby millstones and threw them into the sky, where they remained supsended, but revolving in place as if grinding wheat -- a wondrous sight.
"Can you match that?", jeered the sorcerer. Fair enough, replied the tailor. "See those trees over there? Either you will bend one down, and I will have to keep it down; or vice versa." The sorcerer chose that the tailor should choose a tree, bend its top parallel to the ground, and then let the sorcerer hold it in place. No sooner did the tailor let go than the sorcerer's strength was insufficient; up sprung the tree, flinging the sorcerer directly into the skyborne grindstones, meeting a pulverized and gruesome ending. The crowd cheered; the king looked up, and let the tailor (and all the Jews) go in peace.