Photo Stream and Videos
PhotoStream only syns photos. This is because videos (such as those filmed by the iPhone in 1080p) could easily have file sizes in the gigabytes and it would use up too much bandwidth and online storage for those. Photos on the other hand are just a couple megabytes.

The best thing to do is to download videos directly to your desktop (and you can do this with Image Capture, iPhoto, Picasa, whatever you like).

One alternative is to use Google+ and turn on Instant Upload. That will store photos and videos in a private online album with Google.