Welcome to Android Central! Which phone? Do you mean the shortcut is gone from the homescreen, or you can't even find it in the App Drawer any more? Did the phone come with the Play Store preinstalled, or did you have to manually install it? What downloads are you talking about--apps you downloaded and installed from the Play Store?
Is it possible you logged into the phone as a guest account?