I'm also getting the same problem, I've just purchased a ps4 500GB as I don't plan to have many games on it. I downloaded minecraft in a bundle with a skin pack, texture pack and two theme worlds, Greek and little big planet. I Downloaded the texture pack, went to download the world's and it said I did not.have enough space. Bearing in mind this is the first game I've downloaded on the ps4, there is loads of room!
I then deleted minecraft and reinstalled, managed to download little big planet first but Greek failed and now I apparently have no room, I also now do not have room for texture packs which I was able to.download before.
So apparently my new ps4 only has room for minecraft and 1 add on......... I don't think that should be the case.
Since the most recent update my downloads have now started to work.