The multiple-worlds theory of cosmology allows room for every religion's Heaven and Hell and other planes to coexist, with the similar planes of all the sapient beings of all the worlds in all the galaxies...How often do the wires get crossed, as it were, leaving your paladin in a Hell for hedonistic lizards, for example.
As they travel they notice a horrible rotten smell. As they travel it gets stronger and stronger forcing them to cover their noses and mouth less they choke on the horrible smell. Stream full of dead fish. Spawning trout die in mass quantities after they spawn littering areas with dead fish dying and deteriorating in the sun.