I have very little space on my 16Gb iPhone, however I have a ton of space now in iCloud, how can I move videos from my iPhone to iCloud?
Unfortunately, iCloud will not sync your videos from your iPhone. They will not be available in your photo stream or when you do a restore.
Check out For more reference
You could use a different cloud service.
Dropbox offers 2GB of free space (or 1TB for $9.99 a month or $99 a year) When you connect your phone, it will sync your photos & videos under a folder called "Camera Uploads". Once your videos are in your dropbox account, you can safely delete them from your phone and get that space back.
Also, Google Drive is very reasonable. 100GB for $1.99 a month. Connect your phone and manually copy your videos.