So they estimate economic complexity by the number of discovered Latin documents or inscriptions. Wasn't Greek prevalent in the East?

Which is why the title explicitly names the Western Roman Empire, and the article briefly discusses data issues with Greek inscriptions near the end.

No, based on the professions named within the inscriptions. If a province has relatively many professions that are rare for the WRE, then it's considered more complex. See the paper for the actual estimates, the map in the article does not show the complexity estimation