So I'm a citizen of non-English speaking country, but my master's program in STEM field is fully conducted in English. Should I provide TOEFL/IELTS results when applying for a PhD program in USA or Europe? I accept that it may vary and depend on a university and country, but what should I expect in common?
It is common for a degree from an English-speaking country to exempt you from taking the TOEFL. However, it is much rarer for an English masters in a non-English speaking country to. In the US, the general rule is that they want the degree to be from an English speaking country, although exceptions can be made. It's best to consult the admissions departments of the particular schools you are interested in.
To quote a few websites:
Princeton (emphasis original):
The ONLY exemption for this requirement is if your native language is not English, but you earned (or will have earned before enrollment) your bachelor's degree or a Ph.D. in its entirety in the United States, the United Kingdom, Ireland, Australia, New Zealand, or Anglophone Canada.
A strong knowledge of English is essential for successful study at Harvard, including the ability to understand and express thoughts quickly and clearly. Although you are not required to take the Test of English as a Foreign Language (TOEFL) or other proficiency exams, you may submit your scores if you have done so.
Students who have received instruction in English in their primary and secondary schools and students who have been in the United States for four years or longer and have received a degree from an American institution may be eligible for a waiver of the English proficiency exam requirement by sending a written request to the department or program to which they are applying.
To qualify for a TOEFL exemption you must:
Have a basic degree from a recognized institution in a country where the official language is English.
Have completed a basic or advanced degree at an institution, in the United States or abroad, where the language of instruction is English and the institution is accredited by one of the United States’ regional accrediting* agencies. (United States universities only)
Have completed at least one year of full-time academic course work with a grade B or better at a regionally accredited* institution within the United States.
UChicago (emphasis added):
The English language requirement may be waived if the applicant is a native of or studied in full-time status for at least one academic year within the last five years in the U.S., the United Kingdom, Ireland, Australia, New Zealand or English medium universities in Canada or South Africa. Students who studied in English in other countries, for example, India, Pakistan, the Philippines, Hong Kong, Singapore, etc., are not exempt from the English language requirement.
... been educated full-time in the medium of the English language throughout the two most recent years before the 15 October application deadline, and who remain in full-time education conducted in the English language until the end of the school year in their home country.
If you don't have one of these formal qualifications but are currently being taught in English, please contact one of the College admissions offices for advice.
Nationals of the following [all English-speaking] countries, or applicants who have successfully completed an undergraduate degree (of at least three years duration), a postgraduate taught degree (of at least one year) or a PhD in one of the following countries are not required to complete an additional English language test:
In the UK, you need to provide IELTS results as an evidence of your knowledge of English in order to make a successful Tier 4 visa application. So, even if a University admits you on their PhD program based on your MSc taught in English, the Home Office will still need IELTS results to issue you a visa.
If it is not clear from the advert whether there is an a TOEFL/IELTS requirement, they are unlikely to reject your application for failing to include it - at worst, I expect they would ask for it separately or make an offer conditional upon proof of a certain standard (We have an IELTS requirement and this is what we would do).
Then again, if you already have certification and you believe it accurately reflects your language ability, I don't see any harm in including it as part of your CV.
Since you are applying in Europe as well: I haven't seen any university requiring the TOEFL, but they usually require some proof of English skills. Depending on the country, this can be as lax as your current thesis, a professor from your institution certifying that you can effectively communicate in English, all the way to an official certificate of C2*.
From what I remember, no one asked me for a certified copy when applying, it was enough for me to say that I had it, but some asked you to be ready to submit official proof if accepted. I may be missremembering the frequency, though. Cambridge has a self-verification system: my certificate has a link where anybody can see that I indeed have passed it.
If you have taken the exam, you can definitely add it to your application. Unless they say otherwise, you won't need to pay IELTS to send your scores just for applying.
*To my knowledge, there is no centralised organism in charge of this, so usually any reputable school's certificate is valid.