It could be a pagan temple.
If they were pagans, I do not see why Anastasius does not say it, because 10 years later this designation will be done in Palestine by Christians to Arabs that one knows very well that they were "proto" Muslim and nothing else, therefore monotheists. It was a polemical topos. Here, he points at once a monotheist target in calling the building "synagogue". Because he probably knows that they are not pagans and as the building is not a church, it is, for him, the other monotheist faith in the field, and there is only one.
Read what says Anastasius about the behavior of these Arabs towards the symbols of Christianity. People who do not care and mock them. Furthermore, I'm still searching in the sources attestations of paganism in this area (Egypt/ Palestine) at that time. There is nothing. The discoveries of Nevo in the Negev are interesting, but they have no date. As such, they cannot be used to affirm that pagan Arabs were heavily present at that time. In the 2,3,4, middle 5 th c. yes, later it's seems to me improbable due to the heavily presence of Christianity, from Egypt to Syria. Suffice to read the Nessana (Negev) papyri (People and Identities in Nessana by Rachel Stroumsa, 2008) to realize that in small cities of the desert (Negev) all the Arabs were Christians . Even not Monophysite, but Chalcedonian, and that there is no organized pagan cults any more or unknown to them because residual. Meaning no building.
I really think, Marc, that you should reconsider the system you have built ; each time what you say is refutable by the sources and the common scholarly knowledge, one way or another. Hypotheses must be grounded and the sources on which you ground them should be criticized.To have a scientific attitude is being able to change when one realizes that it does not fit. That it why it is necessary to have no idea, no belief, and to check if it fits with what recounts the sources and what you know of the (long) political and religion history from Palestine to Iraq.
Maybe it does not appear here but I've changed my mind numerous time in the field. I've never thought that one day I will say that Muhammad (as the producer of the Quran in Mecca/Kaba...)had never existed, etc. but it is my serious plunge in the field that made me envisaged the case, because there was too much blank points in the dossier which lead me (and the all scholarship) to go in circles, and this possibility appeared to me, because one is in the field of religion which is a very special field considering what is at stake at that time. I then totally rethought it with this possibility.
With this possibility, I have answers to almost all the questions raised : when... Answers, which fits with each other, therefore which, one time assembled, give a rational and plausible explication to the origin of the Quranic text.