Does a prestigious internship (at google) help for PhD programs in Computer Science?

Take the internship. It's not so much about whether it helps for graduate admissions or not, but rather how it is going to broaden your horizons. If you do the REU program, when you start the PhD, you're going to be doing similar things. On the other hand taking the internship gives you firsthand experience you cannot otherwise get:

• What working in the real world is like
• What skills are actively useful in industry
• What skills you currently lack, but can learn in a PhD
• What kind of job you can do if you get a PhD, but can't do now

(This neglects the financial aspect entirely, plus the fact that you're still going to be learning things during the internship which you can write into your application.) These things are likely to change your view of the PhD entirely. In the extreme case, you might find you don't want to do a PhD anymore. Less extremely, you'll have a better idea why you're studying, what you want to learn, and how that is going to help you.

tl; dr: do the different thing, because it'll act as a great enabler even if it's not immediately helpful.

I was exactly in your position a year before finishing my master’s. I was in touch with Google regarding an internship (I've passed their interviews and could've accepted as soon as we matched me with a topic). The timing for the Google internship didn't fit brilliantly with my university schedule (we had the longest semester in Europe back in the time), so I went to talk to my advisor at the time to ask him whether he thinks I should take the internship despite it colliding with three weeks of my classes.

I was at the time seriously considering following up my master’s with a PhD programme, and he knew that when I came for advice. His response was that if that's my plan, I would benefit much more from a research internship – and then he proceeded to arrange one for me (and one more the following year; he really was brilliant and dedicated advisor).

I agree that through an industry internship you will acquire skills Allure mentions in his answer, and I do admit I lack some of them even now. On the other hand, taking the research internships got me into a PhD programme. Some concrete benefits I got from there (somewhat location dependant):

• I got into my first proper research group. While my master’s advisor was golden, research is not too strong in my country of origin.
• It got me a non-generic, research-oriented letter of recommendation
• Inquiring about PhD positions through e-mail has a very low response rate; even if you don't ask about publicly available information and only ask about advertised positions through proper channels.
• Politely knocking on somebody's door and saying "Hi, I'm doing an internship in the group down the hall and saw you advertising a PhD position. I was wondering if you have five minutes one of these days to talk about it a bit" had a much higher response rate.
• I got coached for the admissions process by my advisers-to-be, as they decided to support me as a candidate following that five-minute conversation mentioned in the previous point.

I do have a feeling the benefits were quite tangible as I come from a fairly small country, my master’s university was not particularly famous and there is not much research support. Thus, being at a research institute and in direct contact with several research groups gave me connections and opened some doors for me which would have been much more difficult to achieve otherwise.

All that said; taking a machine-learning internship at Google will surely not harm your profile or your CV. Just remember – it is a software engineering internship and therefore will give you those skills; if you want to focus on your research skills it is not a best choice. If you want to experience a bit of everything before committing (to a PhD, say), it just might be.

Acceptance on any program is, or should be, based on your attributes, capacities and skills. Ie it is not where you did the internship, but what you learnt from it...