a) If you decide to you could make it so you have to report back to the elder after you kill the destroyer and see the portal. That way you could be notified that the staff had been stolen by the destroyer shortly before you killed him. Which then gives a reason why you enter the portal and why you are looking for the staff in the far east.
The main downside of this is that you have to go through moria twice again...
b) Another way to do it would be to do a cutscene
... (very possible to do right now) It could be made skip-able and would convey the information needed without the tedium of navigating the mines again.c) have an npc turn up after you kill the destroyer (have him start on the stairs and walk to the player) This would be a messenger from Minas Tirith explaining the above.
