For reproducing that exact error, have neither gstreamer1.0-libav nor gstreamer-1.0-plugins-bad nor gnome-software.
To fix the error, one needs both gstreamer1.0-packagekit and gnome-software, then hitting "Find in Software" will open gnome-software with suggestions (as attached).
OK, I was also missing gstreamer1. 0-packagekit.
Summary is:
For reproducing that exact error, have neither gstreamer1.0-libav nor gstreamer- 1.0-plugins- bad nor gnome-software.
To fix the error, one needs both gstreamer1. 0-packagekit and gnome-software, then hitting "Find in Software" will open gnome-software with suggestions (as attached).