Check under Opera Max App Management whether internet access (wifi or mobile, depending on how you access) is blocked for Google Playstore. Although I block internet access for almost all apps, Playstore won't work with access blocked.
When I use opera max on my phone I lose 20-30Mbps of speed on my connection. I expected some loss BUT not that much. Also a little disappointed it's not changing my IP address
Opera Max is a compression service. It will slow down your network because it is using a vpn to tunnel everything sent to your device.
As for your IP not changing, That is with Opera VPN: https://www.opera.com/apps/vpn
You can download it and it will Block Ads, Trackers and Change your IP with your desired country.
My related question: It's fine with me that sites I visit can see my IP, but not fine that my mobile operator - my ISP thus - can see what sites I visit. So, does Max prevent my operator from seeing that? I should think so, because all traffic - even https I understand - go through Opera's servers. As such my ISP should only be able to see Opera's IP, right?