On the gallery module it says No gallery search results found. why is this coming up? See screen shot.

My guess is you're searching the gallery. It only displays that if a search term is present.

My second question, is it possible to create a module for a list of latest videos? maybe do it with CB Activity?

Create a CB Gallery module, set the Asset as desired (e.g. profile.% to show all profile galleries) and turn off the media types you don't want displayed (e.g. turn off photos, files, and music).