I don't think we need to say this, but do not accept that certificate.
Either something is wrong with your connection and you have a man in the middle, or something went terribly wrong on your browser, or some application server at PayPal was compromised.
Since everything looks normal from here, and the certificate is legitimate, don't trust whatever is on the other side.
Can you download the certificate and share it with us, out of curiosity?
Are you using a proxy somewhere? Even if you think you aren't, can you check your network and browser configuration to find it out? You may have malware installed or are using a rogue proxy.
Since the problem was fixed by changing the DNS server to Google's, I wonder what was your DNS server. It may have suffered a DNS cache poisoning, or RAM problems in the server may have mixed up cache entries. But I suspect the former: maybe your ISP has suffered an attack. The output of the host or dig commands, directed at the server, may be useful to debug.
dig www.paypal.com @8.8.8.8
dig www.paypal.com @(your DNS server)
host www.paypal.com 8.8.8.8
host www.paypal.com (your DNS server)
Also: if even your iPhone was having similar problems, the problem is most certainly in your ISP's DNS server. I'm not sure how effective it will be to warn them, but it may be a good idea.
Since all devices connected to the Wi-Fi router are now affected, the problem must lie with the router. A router reset might help fix the problem. If it does not, changing the DNS settings might (e.g. Google DNS or OpenDNS).
If changing the DNS settings doesn't help either (which seems to be the case), I'd assume the problem lies with the ISP's VPN connection that you're required to connect to before you can access the Internet. In that case, you'd have to contact your ISP and let them know about the issue and they'll fix it.
In the meantime, you can connect to a third-party VPN (e.g. CyberGhost VPN) after you've connected to your ISP's VPN and hopefully that'll fix the problems you're facing.
You might also want to confirm that the problem lies with your Wi-Fi connection by connecting a device you know is clean to your Wi-Fi and then visiting PayPal.com on that device. If you still get a ERR_CERT_COMMON_NAME_INVALID or similar errors, you can be sure that your router/ISP is the troublemaker.
Best Answer
The Cyberoam firewall has a built-in anti-virus. This anti-virus is configured to block all unknown protocols going through port 443. Some websites are configured to send different types of traffic through this port, which the anti-virus may not recognize. To disable this feature: