Restore videos backed up to iCloud?
iCloud does not actually backup the videos, only the metadata. The Videos themselves still need to be synced via iTunes or the App Store/iTunes download on the device. 

Like the old backups made in iTunes, the backup contains the metadata, settings and various other bits or pieces that is not part of a normal sync or purchase.

When you restore a backup it will afterwards start syncing the actual media and apps from iTunes, if it is done via iTunes, or start downloading the media and apps from the App Store if you haven't used iTunes for syncing. This does not include videos or music that was not purchased from the iTunes store.

The only videos that are backed up are those in the Camera roll as per this Apple support document. Also note the disclaimer at the bottom:


  Backup of purchased music is not available in all countries. Backup of purchased TV shows is U.S. only. Previous purchases may not be restored if they are no longer in the iTunes Store, App Store, or iBookstore.