When applying to the UK, if you hold the equivalent of a bachelors degree with honours, at first or upper second class, you usually do not need to take a masters degree. I know this as I didn't have a masters, and I was actually advised by my now-advisor that it was not necessary to have one, since a PhD supersedes it.
Having held an internship with a major research company in Silicon Valley, you should be in a great position to apply for a PhD. With your awards and ranking in the class, I'm relatively confident you would do very well in applying for a PhD in the UK. I can't speak for the USA as I'm not familiar with that system, but their PhD program includes what amounts to a taught masters as well.
I can't concur that international students are rejected hugely often. Certainly not ones of your ranking in the class, with awards and significant internships. Even the fact you had a scholarship to study your undergraduate degree is positive in the eyes of admissions teams.
While the process of applying for a PhD differs across countries, if you have a contact at a university you're interested in (or perhaps an idea of a prospective advisor), you should reach out to them. Many universities place the incoming applications into a "pool" on an internal portal, where academics can browse through candidates. I'm sure this isn't the case everywhere, but it's definitely the case at some institutions. If you are able to apply with a specific advisor in mind (who you have communicated with), you have very good chances.
As a small personal anecdote which hopefully shouldn't be irrelevant to this answer, I applied to a named supervisor, with their knowledge, having previously discussed the idea (and actually having met them and discussed it). Having done this, I then understood I was guaranteed to be accepted, given how the opinion of the academic was so significant in their application system.
While this won't be the case everywhere, if you were to apply with the credentials you stated, and it was in a relevant field, I'd be calling you back ASAP. Funding for an international student is sometimes slightly more difficult to organise, but that's not a barrier - actually the majority of our current PhD students are international. This university, while not one of the immediately named top universities, is actually top within a couple of fields. Don't overlook a university without checking where the appropriate department lies on the REF scale (research excellence framework, used to rate the quality of research output).
I'd therefore recommend you look into how the application process works, and plan your submission for any personal statement or case-for-support questions. Having some interesting and well-written answers should be enough. You have industrial experience which you should focus on, as well as your academic performance, and current research experience. That's a lot more than most (accepted) applicants have!