Unable to create iCloud-Backup
The first step I would try after doing what you have done already would be to turn off iCloud backups and restart the phone before turning it back on again.

If that doesn't work, I would try to initiate the backup from iTunes using the Back Up Now button. (I'm assuming you were trying from the iPhone) Go to iTunes and select your device the you should see this: