Ho lo stesso problema, messo DNS ipv4 e ipv6 di google ma ancora non va, secondo me il probema è il DNS ipv6, sembra che non accetta quelli di google.
Per adesso in attesa di soluzione, ci sono due opzioni:
1) per gli smartphone che hanno il menù DNS privato bisogna impostare su automatico
2) disabilitare ipv6 nel router, in questo caso il DNS privato dello smartphone si può impostare anche su no, disabilitare e riattivare il wifi sullo smartphone prima di aprire Galaxy Store.