The concept of the nation-state isn't really applicable to most, if not all governments and institutions from before the Peace of Westphalia, which has a strong case for being a starting point for our modern concept of nationalism. This is especially so for an Empire such as Rome/Byzantium, where an ethnically diverse and cosmopolitan population often comes with the title of Empire. I haven't read Kaldellis' work and definitely will sit down and give it a read myself, but from your description, trying to retroactively apply modern concepts to previous institutions doesn't yield such cut-and-dry results.

The nation-state is very much inapplicable to how the Romans viewed the identity of 'Roman' not as a nationality, but as a status of citizenship and assimilation of peoples into the administration. As a bit of a layman's example, the Late Roman Empire's concept of their identity is not too unlike that of the United States and the American identity. There's a myriad of ethnicities and languages within both borders. But just as Irish, German, Mexican, and English people identity most dominantly as American first before their ethnicity, the same is true for the Roman and later Byzantine Empire, which had a very diverse and cosmopolitan population.

When talking about the Byzantine Empire, the Roman system of government as a whole remained intact throughout the centuries, as did the identity of Roman being a matter of citizenship and participation rather than ethnicity. While the Byzantine Empire was dominantly Greek, the Empire was still largely diverse in its population. There were still sizable populations of Bulgarians, Avars, Serbs, and later Arabs and Turks within the Byzantine Empire's borders actively participating in the Roman government and calling themselves Roman as a result.

I will say that one area where the Byzantine Empire was starkly different from the Roman model of assimilation of peoples was the requirement for adoption of Christianity, and later Orthodox Christianity for its citizens. Christianity played a crucial role in Byzantine life and culture, and one's religion definitely was a factor in Byzantine-Roman identity in a way that the pre-Christian Romans were not. The Patriarch of Constantinople, selected by the Emperor, essentially dictated what was acceptable and mainstream for Christian practice within the Empire, and splinter sects were notably excluded and even persecuted such as the early-Christian Monophysites and later Catholics after the Great Schism. Tensions between Orthodoxy and Catholicism ran so high in Constantinople that organized mobs, sometimes even sponsored by emperors/nobility, would attack Catholics in the city. Most notably when Emperor Andronikos Komnenos led a mob to massacre many of Constantinople's Catholic merchants in 1182 (an event that was remembered by many Catholics in 1204, when Crusader armies sacked Constantinople fueled partly by retribution).

To sum it up, the Byzantines certainly didn't view themselves as a monolithic Greek nation-state, but as a cosmopolitan state where Roman was still an identity of citizenship and participation in administration rather than something of nationhood. The Byzantine Empire was a monolithic theocracy however, viewing themselves as ruled by God directly and through the Emperor and Patriarch, and the adoption of Orthodox Christianity as described by the Emperor and Patriarch was very much encouraged, with other faiths being subject to discrimination as an 'outsider' or 'other' rather than the modern nation state's dichotomy of 'us vs. them'.

Sources:

The Byzantine Theocracy by Steven Runciman

Studies on the demography of the Byzantine Empire by Peter Charanis

Byzantium and Venice: A Study in Diplomatic and Cultural Relations by Donald M. Nicol

Edit: typos