Saint Kaleb's inclusion into the core liturgical stream of the Greek Church was solidified with the compilation of the Synaxarion of Constantinople (Synaxarium Ecclesiae Constantinopolitanae), put together during the reign of Emperor Basil II (976–1025 CE).
From what we know about the ecclesiastical history of Ethiopia they did not have any mainstream practice of monasticism in the kingdom until the arrival of the Nine Worthies in the fifth century. These were Miaphysite monastics from the Eastern Roman Empire who fled after Chalcedon. Settling in the Aksumite Kingdom, they played a massive role in expanding Christianity, establishing monasteries, and translating religious texts into the Ge'ez language.
King Kaleb led an invasion into Yemen around 520 against the Himyarite king Dhu Nawas, a Jewish convert who was persecuting the Christian community of Najran. After much fighting, Kaleb's soldiers eventually routed Dhu Nawas' forces. They killed the king, allowing Kaleb to appoint Sumyafa Ashwa, a native Christian, as his viceroy of Himyar. Ethiopian tradition states that Kaleb eventually abdicated his throne, gave his crown to the Church of the Holy Sepulchre at Jerusalem, and retired to the monastery of Abba Pantelewon which was founded founded by one of the Nine Worthies.
Monastery of Abba Pantelewon
King Kaleb's son and successor as Emperor of Ethiopia Gebre Meskel commissioned one of the Nine Worthies Abuna Aregawi to found the monastery of Debre Damo in the Tigray region of Ethiopia.
Abuna Aregawi
Monastery of Debre Damo
Given all this information how can we justify accepting King Kaleb as a saint when he was clearly a Non-Chalcedonian?