As I discuss in this answer to a similar question, there is no indefinite article in Greek. A literal translation would be "God."1
They were waiting for him to swell up or suddenly fall down dead. But when they had waited a long time and saw no misfortune come to him, they changed their minds and said that he was [a] God.
A translator's decision to render μεταβαλόμενοι ἔλεγον αὐτὸν εἶναι θεόν as "they changed their mind and said he was a god" reflects a translator's theological monotheistic position. There is one God and all other gods are a god.
In addition, "they changed their minds and said he was a god..." implies those speaking understood a monotheistic (or possibly supreme) "God" to which all other gods, were a god. There is no evidence to support this was the case.
The fundamental challenges to putting "a god" in the mouths of the Malta natives are twofold. First, as there is no indefinite article it implies a conceptualization for which there was no word. Arguably, if there is no word to express an idea or concept, it is because that idea or concept has not yet developed to the point where it is articulated. The second challenge is that polytheism is not "gods" in general but specific gods with specific attributes which controlled the natural world. One did not invoke "a god" for rain, or fertility, for example: one called upon the specific god whose province was rain or fertility. One could say "a god" as an indefinite deity was not in the Vorlage of people because "god" was always in some way, specific and definite.
"A god" was not linguistically possible since people think in terms of a single god generically. Polytheism is a belief in multiple gods, each of which have specific identity, name, position, characteristics, and so forth. For example, it is impossible to believe someone who believed in multiple gods would decide to offer a sacrifice to "a" god. Either their act would be to a specific god or described simply as to God or the gods. The language did not have an indefinite article because people did not think in those terms.
1. A second issue arises over capitalization. The original manuscripts would have been written in block letters so it would be impossible to differentiate God from god. Like the decision to insert "a," capitalization is an interpretation.