Well, that was also back in 2nd edition D&D. 5th edition Paladins don't actually have to serve a god, their power comes from their oath.
Though if I'm remembering my Forgotten Realms lore correctly, most people in the setting, incvluding paladins, do have a patron deity that they primarily worship (as I recall there's a very unpleasant afterlife waiting for people who followed no god at all, but it's been a few years), and there's a few gods that are obvious patrons for Paladins. And the stuff to do it is clearly there, I used a mod to play as a paladin of Selune and it worked fine all game. No idea why the option was removed, but my best guess is that it was an attempt to have unique dialog options for clerics, since the paladin options seem identical to the cleric ones.
