I had this exact same problem a while back. I finally found a soluti, which did the job for me. You will need a root file manager like the one included in TOM toolbox (https://play.google.com/store/apps/details?id=com.jrummy.liberty.toolbox). When you open the root browser you need to go to data–>app-lib and erase whichever app you can’t update or install. Afterwards go to the play store and download it.
I hope that helped.
Maybe a good tip SirLukeSchande 
In my case, I solved the problem… by installing Cyanogenmod
I’ve tried all the things you say, but my phone on google plays keeps saying ’ insufficient storage error’ , even if hough I still have like 249 MB left. I’ve got a android smart 4 turbo - how do I solve this?
@Amalka_Slavikova, do you have a Fairphone?
Because everything writen on this forum is for users with a Fairphone.
Like @Lidwien says this is a Forum about the Fairphone. Also this topic is quite outdated.
If you do have a Fairphone and have this issue following two topics are more up to date atm:
Insufficient storage error even after partition upgrade for FP1
Memory is full
This topic is now closed. New replies are no longer allowed.