Google has just approved and published the Companion It will arrive to your phones in the following minutes. Else Clear Cache and Force Stop of Play Store
Update Completed