It doesn't even need to be a god, or make sense!
In a storyline in which Shazam was dead, Freddie Freeman was in a race with Sabina, a battle witch descended from Merlin, to gain the power without a middleman.
In that storyline it was revealed that the entities that Shazam acts as a middleman for are "
Lords of Magic."
The lords of magic are not deities, but more conceptual like the Endless. They allow such deals as with Shazam because a champion embodying their concepts increases the presence of their concepts in the universe.
So Solomon who is the patron of Shazam is the concept of the wisdom, the Achilles who is a patron is the concept of the invincibility, just as Hercules is the concept of strength, Mercury is the concept of speed, Atlas as the concept of stamina, etc, etc.
Hercules the lord of magic is embodied on Earth as a latino convict, King Solomon is a female tattoo artist, etc.
And possibly not as hard to kill as gods, since Atlas was killed by Sabina with her dagger of "stab a bitch and steal their mojo."
Now the sword of nemesis can do the same thing, even on gods (Wonder Woman was the goddess of vengeance for all of five seconds thanks to it), but if you have a dagger of killing gods and stealing their power, why fight with Freddie to get the power of Shazam instead of just going highlander on any deity you can find?
Not that there is any indication that Zoat is using that here, because if so Teth Adom certainly hasn't noticed.
Sure Paul interacted with them, it's not like Paul has the occult chops to tell the difference between a deity and a conceptual entity of the same name.