You CAN change your undergraduate GPA by taking undergraduate courses. Its called a post-bac. And don't pursue a PhD as an application enhancer. Its a terminal degree to become a scientist. That's a 5 year degree toward a job you don't want to be the cherry on top for a medical school application. Volunteer (where you are doing something and helping people), and ace some hard upper tier science at your local college - that's what you're missing.
I'm truly sorry you had this bomb dropped on you. You clearly put a lot of work into the MCAT, shadowing, and pre-writing but its the truth. Either you've had CRIMINALLY BAD advising, or you saw what you wanted to see.
I'm was multi-time reapplicant (~3.55 GPA, ~515 MCAT, lotsa research) and I was definitely guilting of seeing what I wanted to see and doing what what was most comfortable. I thought that maybe if I used enough jargon ("stereotaxic surgery", "PCR, etc.) in my essays they would think "well we have enough plebes who volunteer. This guy can be the smart one!" So I went in with maybe 100 hours of clinical volunteering and no non-clinical. Perhaps you, or someone else, simply thought it was implicit that master's courses trumped undergrad. Maybe shadowing seemed more comfortable, after a time, than finding a new volunteer gig to discuss passionately. I don't meant to dump on you but I mean to highlight the importance of lots of different eyes on your application and progress.
Going forward:
1) At this point you've done all the work. If you have $2000 to burn... will being a re-applicant really hurt you in a few years when you've improved your app, if you choose to apply again? That is for an experienced adcom to say.
2) You could spend a few years trying to repair your GPA and go DO.
@Goro has a
guide for reinvention. I don't know if it applies to internationals. If you're finishing up a graduate degree I'm guessing you're in your mid-20's? That's going to be even more school and debt for you.
3) If you have 4 first-author papers to the point of submission you probably have what it takes to be a successful researcher? You've a strong resume in that area at least.
Again, sorry.