I reach a different conclusion than the currently accepted answer.
I interpret any form of doorway or magical portal to shorten distances (it's their purpose, after all) so that any celestial, fiend, or undead might be within the 60' range of the Paladin through the Gate portal. That spell provides
... a portal linking an unoccupied space you can see within range to a
precise location on a different plane of existence. (PHB p. 244)
There is a generic description of a portal.
Portal is a general term for a stationary interplanar connection that links a specific location on one plane to a specific location on another plane. (DMG p. 45)
There isn't a great deal of other detail on the mechanics of portals to other planes.
If a character can move in one turn with 30 feet movement to a different plane I would consider that to be only 30 feet range to begin with; it doesn't matter if the destination is the other side of a doorway, a different room, a different street, or a different plane. The visibility part of Divine Sense is the concern : "...that is not behind total cover"
If the ruling is that people actually can see through the portal and check what is on the other side (and the Gate spell does describe "...You can orient the portal in any direction you choose." which would make only sense if it can be adjusted depending on what is visible on the other side) AND there is no full cover for the creatures (as example, a wall on the other side in a building on the other plane) then Divine Sense could work.... however, if you need to look through the portal then you can already consider anything outside the view from portal to be in total cover, so the only use of Divine Sense would be if the spellcaster looks around with the portal as with a periscope, finds a few creatures in the view from the portal, and then the Paladin would use Divine Sense to check if the visible creatures (through the portal) are celestial, fiendish, or undead.
This is not much better than full denial of the use of Divine Sense, though if the creatures can be seen through the Gate the Paladin can at least identify if they are disguised. This could help find enemies hidden among slaves on that plane which the party wishes to free, or if the party looks for a specific celestial being they can at least pinpoint celestials, even among a large mass of people at a marketplace (as example).
A Gate allows a creature to move to a different plane so of course many would attempt to trick a caster to let them cross over. A paladin can as such still help avoid bad things from happening, but the 'periscope' limits sight and use of Divine Sense.
The other concern when making this ruling is if a given portal is the same as the one provided by the Gate spell, or if it has other features. The rules appear to be silent on that level of detail.