I have a Lenovo Android phone with 8GB of space, but I can't download, upgrade or even store more apps. It tells me that I have insufficient STORAGE
If it's possible, insert an SD card and move apps to it.
In case you have android marshmallow, you can insert the SD card and set it as your internal storage.
You can also try to clear the cache of your device.
If your device is old enough, you could think about rooting it and uninstalling bloatware apps. You can remove system app without root (with adb), but it works shit.