I think you have an excellent profile. All you need to do is focus on what you really want to do later in life. If it's academia, go for the PhD, otherwise, an MS would probably be enough, at least for now, and later you can decide wether you want to pursue further study or not.
It's a bit late now, but I think it wouldn't hurt to re-take GRE to help verbal / AWA. However, I know that foreign students tend to get away with lower scores here, but the same doesn't always apply to locals.
Oh and if you're into combinatorial optimization I'd definetely add Georgia Tech to the list. Their deadlines are still over a month away.