Well there are several things you can do to solve this problem (or, at least, to understand WHERE it is).
The simplest I can think of are:

1. Go to Settings -> Storage and see how the space is being used. Chances are you have one or more apps that use to download a lot of contents so you should find that the major part of your storage is occupied by "Miscellaneous" files. In this case you just have to tap on the related voice and you'll see a list of app and their data;
   
2. Reboot your device into recovery mode and clear cache;
   
3. Long press on Play Store -> Settings and clear its data;
   

The last two ideas come from the fact that sometime Play Store and similar apps (Settings app too) give problems messages only because the cache is full of data (most of which is merely made up by useless things)...

Just try and tell me if one of these three things works ;)

Well there are several things you can do to solve this problem (or, at least, to understand WHERE it is).
The simplest I can think of are:

1. Go to Settings -> Storage and see how the space is being used. Chances are you have one or more apps that use to download a lot of contents so you should find that the major part of your storage is occupied by "Miscellaneous" files. In this case you just have to tap on the related voice and you'll see a list of app and their data;
   
2. Reboot your device into recovery mode and clear cache;
   
3. Long press on Play Store -> Settings and clear its cache;
   

The last two ideas come from the fact that sometime Play Store and similar apps (Settings app too) give problems messages only because the cache is full of data (most of which is merely made up by useless things)...

Just try and tell me if one of these three things works ;)