Re: What to do?
First, the phone. Completely wipe it. Backup any contacts/pictures using a PC with good anti-virus and scan the backup folder after completion. Depending on the skillset of the programmer, anything you pull off that phone right now may have code injected to re-infect/spread the code if put on a "clean" device. Doubtful, but be prudent.
Hard reset the phone: Walkthrough for Android
Re: Microsoft Accounts
Get them recovered and set a strong password. Use the online recovery options
and contact Microsoft if needed.
Re: Finding the attacker
It's unlikely anything will result from this; but you could contact your local FBI field office and report the crime. They're able to take an image of your phone for evidence or they might take it and hold it for a certain amount of time. Either way, they have the data. The local police have the same capacity, but the chances of them pursuing an investigation, and having the resources to conduct, are lower.
I would venture to assert that your friend wasn't a target specifically, but more likely this resulted from downloading a "free" app onto the phone, which then provided access to other accounts. My Xbox live account was compromised that same way and it took months to get everything straightened out and charges refunded. Contact Microsoft, recover the account(s) and change all passwords.