Source: TW
In the 680s they were still trying to stamp out paganism in Greece and Anatolia. Entire campaigns devoted to that.
Pagan persistence
Most of it got ignored and there were even elite pagans like Zosimus in the 6th century when it was nominally illegal.
Keep in mind even when Theodosius effectively made any other religion illegal, the Roman senate was almost entirely pagan institution and had been ineffectively trying to fight christian persecution for decades. Like when the image of Victory was removed from the Senate. Many elite pagans, and also those beneath notice like poor city people, country people, and slaves, were left alone if they didnt cause trouble. Temples were officially closed but this was sometimes ignored and people made due without official temples.
Augustine mentions people worshiping all sorts of other gods, all after the edicts of Theodosius. And quite openly down in Africa where he lived. And not all Christians were state church christians either.
Justinian
Justinian in the 6th century decided to systemically go after anyone and everyone who did not fit his definition of orthodoxy. He went after elite and fairly harmless institutions like the Academy in Athens. These philosophers werent a threat to the state and had been ignored.
He went after little churches and those who had dissented from the state church on some minor point of doctrine at any point. He went after gnostics. And he went after the very numerous and rich Arians. They had mostly been left alone after so called orthodoxy secured power. Persecuted at times yes, but the Arian churches were numerous and had many elite adherents. And the Arian Goths in the West(who ruled Africa, Spain, and Italy) would persecute their orthodox populations if the Eastern emperor persecuted Arians.
Justinian went after overlooked pagans and even private worship of the ancestors and lares. Even tried to ban customs that had derived from pagan practice. No one was safe.
Justinian had a habit of actively pushing his religious ideas onto the bishops and he actively influenced church policy. Justinian had a habit of exiling bishops who contradicted him. As did Theodora.
I find it ironic many orthodox later on considered Justinian himself a heretic.
Beliefs
Well, he favored ideas that were later on decided to not be orthodoxy. He got Origened.
His wife Theodora was a Monophysite (later decided to be a heresy) and Justinian favored this as well, wanting to bring Monophysites back into the fold.
Justinian also thought Jesus’ body wasnt that of a normal human. He believed, as many earlier Christians, that Jesus was superhuman and his physical body wasn’t mere mortal flesh.