В меню, где сетевые подключения нету пункта
Трудно понять что там за меню вы рассматирваете, но похоже, что это Network Manager...
Прежде чем ним устанавливать соединение, вы должны быть уверены, что:
 - ваше устройство вообще видится:
$ ls usb
...
$ dmesg | tail -n100 | grep usb
...
- оно переключилось из устройства инсталляционного CD-ROM в режим AT модема:
$ ls /dev//dev/ttyU*
...
$ ls /dev/ttyACM*
...
Всё очень зависит от конкретного типа модема, который вы не указываете.
А дальше см. 
Установка и настройка USB-модемов
P.S. 
Почти все модемы можно заставить работать ... но будьте готовы к тому, что есть ограниченное число модемов, которые вы 
не сможете заставить работать в Linux.