Carmack (1981, p. 44) suggests that the Popol Vuh describes the journey of the K'iche' forefathers from a Chontal-speaking epi-Toltec center on the coast of the Gulf of Mexico, probably in the modern-day Mexican states of Veracruz or Tabasco.
The mention of "Mexico" in the PV seems to support this, saying "[t]his they said among themselves as they remembered their older borthers and their younger brothers, the Yaqui people. These dawned there in Mexico, as it is called today. Thus surely a portion of them remained there in the East, they whose names are Tepeu and Oliman" (Christenson, 231).
It is worth pointing out that "Tepeu" and "Oliman" are both names of Nahua origin, like "Mexico" itself. Although the Gulf Coast region would not be placed to the east of the K'iche' area on a modern map, the authors of the PV seem to have regarded it as such. On the complex ways in which speakers of Mayan languages orient themselves in space, and how indigenous cartographies and spatial vocabularies were misunderstood by colonial Spanish authorities, see Solari, "Circles of Creation."