The most important thing to remember is, this is a silly joke comic. For the funsies and the japery.

However, in the specific: 5e Paladins can get their power source from anything (including "their own self-belief" - "a paladin’s power comes as much from a commitment to justice itself as it does from a god".) so a Paladin devoted to a Djinn would be completely fine.