I'm going to post an alternative answer to my own question, in spite of having accepted the previous answer. The reason is that I have since learned, on my personal device, that the Android Backup and Restore doesn't work as well as I expected, so while that wasn't the case in the case above, this might be the case for other people finding this question.
Apparently, if restoring on a different device or even on the same device with a different OS, it won't restore anything but system data. This happened to me when I wiped my Moto X (2nd gen) to install LineageOS on it.
That means that notification settings, WiFi passwords and background images will get saves, while app data (save games, app settings, etc) will not.
I'm not sure if newer versions of Android come with better Backup and Restore functionality, but for now I'm going to be using a specialised backup app (Helium at the moment) to keep my data fairly backed up, and also use that when transferring to a new device.
If anyone has any positive experiences with Android own Backup and Restore actually restoring app data on a new device, please share any details of android versions and device :)
Update on Helium
Here's a few words on my experience with Helium so far.
At first I was a bit disappointed, due to a few limitations of the app. Using the free version you can't setup a scheduled backup, so I had to start it manually every time. This, however, became extremely tedious, as you can't save a "selection" of apps to back up, and so had to scroll through all your apps each time. So I bought the premium version, so I could set up scheduled backup tasks.
But for some time this also didn't work, because the app kept losing "authorisation" or whatever it is, so I had to connect it through USB with USB debugging enabled and running the Helium desktop app every time I wanted to do a backup. And you can't just trigger a backup, only change the scheduled time until "in a minute" and wait...
Then that seemed to stop being a problem, and authorisation isn't lost any longer, even over restarts. But another problem is that the backup can't run if the screen is locked. I'd like to have the backup run automatically in the night, while my phone is charging and on WiFi, but I only wake up to a message about the backup not having been able to run, because of the screen lock. This is easier to fix, by simply tapping the message to run the backup, but means I then have to leave the phone until done.
Over all it works and I'm glad I've got backups (backing up to Google Drive), but it could work a lot better.
I still haven't tried restoring, so there might be a call for another update when I've seen how well that works :-)
Update 2 on Helium
It's started losing the authorisation all the time again, which means that the automatic backups aren't happening, and I have to re-authorise and re-schedule to "now" to trigger them. Would be great to hear from any other Helium users out there, if they have some experiences with this.
Update 3 on Helium
It's not losing authorisation as much, which is probably because my phone isn't restarting as much (I've got a new battery). Also, there have been some updates to Helium, so now you can save selections of apps, which is really handy if you want to update which apps you backup in a recurring backup (almost as handy as if you could edit the recurring backup's settings).
02-21 14:20:44.034: V/BackupManagerService(914): restoreAtInstall pkg=<package> token=c restoreSet=1 02-21 14:20:44.037: D/BackupManagerService(914): MSG_RUN_RESTORE observer=null 02-21 14:20:44.037: D/BackupManagerService(914): Starting restore. 02-21 14:20:44.690: E/BackupManagerService(914): Required package metadata but got 02-21 14:20:44.700: I/BackupManagerService(914): Restore complete.