The storage on iCloud is irrelevant. What you need is storage on the iPhone. Connect the phone to iTunes on your computer using the USB cable (or WiFi if you have set that up previously). Click on the name of the phone, then look at the chart at the bottom of the screen. If will show you how your phone's memory is allocated.