Today I had to do this for an isolated network, it was a great reminder 🙂
https://social.technet.microsoft.com/Forums/windows/en-US/5a69ed0c-2fcf-483c-ab1d-ad5b16fa32ca/isolated-network-without-internet-access-how-do-i-make-the-yellow-no-internet-access-icon-go?forum=w7itpronetworking
I had some missing GPO templates (2008 R2 server) which are easily obtained from Microsoft
Installation is straight forward and explained under Install Instructions.
And yes, you need both policies enabled.