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.
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?