Absolutely they can. Carriers have access to the system partition aka We do what we want (hopefully they do what makes sense). This is how bloatware is installed (the things you can't get ride of).
Your thinking is tainted by the american model where you buy carrier locked phones. But no, that is not usually how it works. The system partition can be modified by the party who issues system updates. Normally this would be the company making the phone, such as Samsung. But in the US, some carriers sell modified phones locked to their network, and in that case the carrier is also the one shipping updates.
Worked at Sprint back in the day and we (I) had to do this. Special certificates to produce a special OS build with the right privileges (carrier specific). The carriers and builders (Samsung etc) work together to get this in place. That on top of zero rating data being sent out for tracking allow the carrier (or builder) to do what they want.
Are you sure this is the case? All the carrier app loading implementations that I am aware of (this is a small number) explicitly whitelist some carriers or even some apps by certain carriers. For instance, the implementation I worked on myself (as a reviewer) only granted a single carrier to load one of their apps when the SIM card was inserted.
With that implementation, it would not be possible for any random carrier in a foreign country to load random bloat onto my phone just by me crossing the border to that country.
