Neeraj,
Unless the Microsoft Authenticator app is badly corrupted, it's typically easier to simply open the app, select the Microsoft account listed that was installed first by mistake, then select the gear icon in the upper-right-had corner of that screen and click "Remove Account' which clears that portion of the app information.
This has the same basic effect as clearing the cache, after which you simply restart the app or the entire phone to ensure everything related to the account is gone before following the Restore procedure correctly.
Only if that option doesn't exist would I bother to use your 'hammer' approach to try and obliterate everything related to the app, which really wasn't the problem here in the first place. It's not following instructions, or more likely knowing they existed, that typically results in this problem.
Rob