Two modern scholars, in their analyses of this obscure reference to the character in question, both point out a certain apocryphal connection between Eurymedon and Hera.
In his 1993 book Early Greek Myth: A Guide to Literary and Artistic Sources, Timothy Gantz discusses (on p. 57) Scholion Ab for Iliad 14.295-296, which he tells us is "credited to Euphorion", as well as part of Scholion T. The story told in these scholia
suggests that Hera, while in the house of her parents, was raped by
Eurymedon (one of the Gigantes) and bore Prometheus, to whom Zeus was
thus understandably hostile.
(In this section of the same chapter, Gantz contends with the potential chronological issues involved in having this event transpire in Hera's parents' house, considering the other much better known story that renders Hera undoubtedly unavailable for this piece of drama because she would have been trapped inside her father's belly at the time.)
According to Robin Hard, writing in The Routledge Handbook of Greek Mythology: Based on H.J. Rose's "Handbook of Greek Mythology" (2004: 88), "Homer alludes to Gigantes on three occasions in the Odyssey." In the third instance thereof,
we are told that a certain Eurymedon once ruled over the over-bearing
Giants but brought destruction on himself and his people (in unstated
circumstances). There is no reason to suppose that the latter story
has anything to do with a revolt against the gods... According to a
tale ascribed to the Hellenistic poet Euphorion, Hera was raped by the
Giant Eurymedon while she was still living at home with her parents
and bore to him Prometheus as a son. When Zeus came to learn of this
after marrying her, he hurled Eurymedon down to Tartaros and ordered
that Prometheus should be thrown into chains, using his theft of fire
as a pretext. The obscure reference to Erymedon (sic) in the
Odyssey must have inspired the invention of this revisionist myth.
When I first read about the Giant Eurymedon I assumed that his story was the same as that of the Gigantomachy, or at least closely connected to it in some way. Aaron Atsma of The Theoi Project website seems to have arrived at the same conclusion, saying that Eurymedon "was probably the same as Alkyoneus or Porphyrion who are named as the king of the Gigantes by other writers."
I have found no ancient reference to Alkyoneus [Alcyoneus] as any kind of king, although he does seem to have been a special sort of champion among the Gigantes, bearing the unique invincibility of bouncing back from death upon being slain on his home turf. He is similar to his half-brother the giant Antaios [Antaeus] in this, except that Alkyoneus had to be dragged across the border of his land in order to put a decisive end to this uncanny power of resuscitation.
The most direct link between Eurymedon and Alkyoneus is that both are said to have had a number of daughters, an unspecified number in the former's case while Alkyoneus is credited with seven. None of Alkyoneus' offspring, however, is named Periboia [Periboea], as is Eurymedon's youngest, thus making that link more tenuous.
In the case of Porphyrion, Pindar does explicitly call him "king of the Gigantes". Apollodorus, in his account of the Gigantomachy, relates the somewhat bizarre stratagem employed by Zeus in the fight against his enemy leader.
Porphyrion rushed against Herakles [Heracles] and also Hera. Zeus
instilled him with a passion for Hera, and when he tore her gown and
wanted to rape her, she called for help, whereat Zeus hit him with a
thunderbolt and Herakles slew him with an arrow.
The coincidences of details between the narratives of Eurymedon and Porphyrion warrant the raising of at least one eyebrow, I would say: each one is a Giant king who is said to come to a bad end after violating Hera (or attempting to do so), with Zeus playing a major role in either story.
Also, the introduction to your Question might allow that Eurymedon is merely a title rather than a proper name, perhaps for King Porphyrion "Who Rules Far and Wide." Eurymedon is after all an epithet of the hero Perseus as well as the gods Poseidon and Hermes.
An ancient work called the Recognitions is (apparently dubiously) ascribed to Clement of Alexandria, who would have written in Greek. However the Recognitions survives presently only in Latin translation, and in its 10th book, Jupiter (i.e. Zeus) is said to have had a son named Coron [Koron?] by Leandia [Leandeia?], "the daughter of Eurymedon". It's a pet speculation of mine that this is the Giant Eurymedon and thus that Leand[e]ia is one of the Odyssey's unnamed sisters of Periboia.