How to fix "This Device isn’t Play Protect certified"

Prequisites:

Go to Settings > Other > About and take a note of the GSF ID or use Device ID
Open https://www.google.com/android/uncertified in any Web Browser
Log in with your Google Account
Enter the GSF ID
Solve the reCAPTCHA
Tap Register
Restart your Device
Wait a few Minutes
Open Google Play Store > Settings > About > Play Protect certificate still shows Device is not certified but it works