What is your phone model. You should post more details you think relevant.
Try following options one at a time..
--->Make sure you have correct DATE and TIME and TIME ZONE.
--->Try switch off, then restart.
--->Make sure you have a correct and working gmail account used in your phone.
--->Clear cache and data of your google play app.
--->Do a backup and perform a FACTORY RESET
Welcome to Android Central! Is the exact message "Service not supported on your device"? Does it show up as a "toast" notification (i.e., a window in the middle of the screen), or a notification in the status bar?
Go to Settings>Accounts. Is your Google account listed there?