Alpenglow = 'a reddish glow near the horizon opposite of the Sun when the solar disk is just below the horizon' (Wikipedia). Since the Sun has already gone below the horizon, this effect is brought about by light being reflected off precipitation or ice crystals in the air. The effect is most notable in mountain areas, where high mountains in the east are lit by the effect.
The Belt of Venus is a form of Alpenglow where the shadow of the Earth from the setting Sun causes the band of reddish colour to be separated from the horizon by a twilight-y darkness, giving it a more arched shape.
Since the writer is in the desert, this could possibly be happening in the Atlas mountain countries of North Africa.
You were navigating with your compass and walking east.
There are the remains of a meteorite that crashed there in 2008.
Fragments of it had been strewn across the desert as it broke up.
As sunset approached you walked past a lump of it.
The magnetic material of the meteorite affected your compass.
Suddenly, you realised you were walking towards the sun!
But you know that the sun cannot set in the east.
So you ignored the compass and continued walking away from the sun. After a while the compass needle moved back to where it should be.
And so the sun set in its rightful place...
Passed through the Est Region in Burkina Faso at sunset.
When you say "the sun was setting in the East", you are referring to seeing the sun set in a place called the East. Given that it needs to be close to a desert and near the Equator, the Est Region (Est being the French for East) fits the bill perfectly.
You are very close to the North or South Pole, and close to an equinox.
From near the poles the sun appears to almost describe a circle close to the horizon, rising and falling slightly relative to the horizon. Identify the direction in which the sun is descending. You can than make that direction 'East' by simply walking around the pole until you at a 90 degree angle of latitude relative to it.
For example, let's say it's close to an equinox and you are standing on the (geographic) North Pole. You see the sun describe an almost-circle around you, rising and lowering slightly. You observe, for the sake of argument, that it crosses the horizon in the direction of the Greenwich meridian. You can make the Greenwich meridian 'East' by simply walking a few steps down the 90 degree West meridian.
This is another possibility, though probably wrong, but I'm thinking you were:
behind a large natural arch of some sort. The sun was actually rising to the east, but as it passed behind the arch, you could say that it was technically setting, relative to the landscape behind you. You did say "for a while", meaning that as it continued to rise past the arch, it actually "rose" again and continued its path across the sky. Had you stayed there all day, it would have set a second time, in the west as one would expect. I've illustrated how it would work here: (facing east)
You could also have been:
in an eastward facing cave mouth, for the same reason.
While unlikely, it's possible that you saw a mirage or similar visual phenomenon - differences in air density meant that the sunrise occurred earlier than anticipated, but as the Sun heated the air it also changed the airs refractive behaviour, causing its image to set again (albeit briefly).
the "East" or the "Eastern World" an area traditionally comprising anything east of Europe. https://en.wikipedia.org/wiki/Eastern_world.
So looking in the cardinal direction West to watch the sun set it would appear to briefly set in the land of the "East".
This is my second, different (but incorrect) answer, based on an experience in USA.
I had hitched a ride east and was lying in the back of station wagon, looking out of the rear window. We were motoring across a rolling landscape and the sun was getting lower in the sky. Eventually as the road went down into a hollow the sun dipped below the horizon. When we went back up the other side the sun rose again (in the west). The scene repeated several times, until finally the sun failed to rise again. That evening I watched sunrise a dozen times, but in the west!
Now imagine walking towards the east. The sun rises in the east, and the path makes a dip into a hollow. As I walk down, the sun sets in the east. A few minutes later the path makes the slight climb out of the dip, the sun rises again, and by now is high enough that it does not "set" again.
The flaw in this solution is that the question states "in the evening".
Seeing the sunset in the East, is not refering to the position of the sun, but rather the posistion of the event. If you were at great height, you might be able to observe that in the East the sun is setting, it is getting dark and the ground it taking a distinctive red hue. Whereas to the West it can be seen that the Earth is still enjoying afternoon daylight. In effect you can see that the sun it setting in the East, and not yet (for a while) in the West.
Such a view might be plausible from
a desert at great altitude such as the Tibetan plateau.
You were walking really, really fast towards the west. Faster, in fact, than the rotational speed of the Earth, so the Sun would appear to be rising from the west, then setting in the east. Of course, walking at this speed is pretty tiring, stopping to rest puts the Sun back on it's correct path and setting again in the west...
At the place you were, it was the evening. But at the same moment, further East, it was dawn : the Sun was setting.
You could have rephrased your sentence as : "Where I stood, it was the evening, but in the East, the Sun was already setting."