Just tested with latest Rawhide updates and current Linus kernel, slightly different output but the end result still the same:

Apr 19 16:59:55 localhost kernel: usb 1-8: new high speed USB device using ehci_hcd and address 4
Apr 19 16:59:55 localhost kernel: usb 1-8: New USB device found, idVendor=0421, idProduct=010e
Apr 19 16:59:55 localhost kernel: usb 1-8: New USB device strings: Mfr=1, Product=2, SerialNumber=3
Apr 19 16:59:55 localhost kernel: usb 1-8: Product: Nokia E75
Apr 19 16:59:55 localhost kernel: usb 1-8: Manufacturer: Nokia
Apr 19 16:59:55 localhost kernel: usb 1-8: SerialNumber: 1234567890
Apr 19 16:59:55 localhost kernel: usb 1-8: configuration #1 chosen from 1 choice
Apr 19 16:59:55 localhost kernel: cdc_acm 1-8:1.1: ttyACM0: USB ACM device
Apr 19 16:59:56 localhost NetworkManager: <info>  (ttyACM0): found serial port (udev:GSM  hal:)
Apr 19 16:59:56 localhost NetworkManager: <info>  (ttyACM0): deferring until all ports found
Apr 19 17:00:00 localhost NetworkManager: <info>  Re-checking deferred serial ports
Apr 19 17:00:00 localhost NetworkManager: <info>  (ttyACM0): new Modem device (driver: 'cdc_acm')
Apr 19 17:00:00 localhost NetworkManager: <info>  (ttyACM0): exported as /org/freedesktop/Hal/devices/usb_device_421_10e_359557010249049_if1_serial_unknown_0
Apr 19 17:00:04 localhost NetworkManager: <info>  (ttyACM0): device state change: 1 -> 2
Apr 19 17:00:04 localhost NetworkManager: <info>  (ttyACM0): deactivating device (reason: 2).
Apr 19 17:00:04 localhost NetworkManager: nm_system_device_flush_ip4_routes_with_iface: assertion `iface_idx >= 0' failed
Apr 19 17:00:04 localhost NetworkManager: nm_system_device_flush_ip4_addresses_with_iface: assertion `iface_idx >= 0' failed
Apr 19 17:00:04 localhost NetworkManager: <info>  (ttyACM0): device state change: 2 -> 3
Apr 19 17:00:12 localhost NetworkManager: <info>  Activation (ttyACM0) starting connection 'Auto Mobile Broadband (GSM) connection'
Apr 19 17:00:12 localhost NetworkManager: <info>  (ttyACM0): device state change: 3 -> 4
Apr 19 17:00:12 localhost NetworkManager: <info>  Activation (ttyACM0) Stage 1 of 5 (Device Prepare) scheduled...
Apr 19 17:00:12 localhost NetworkManager: <info>  Activation (ttyACM0) Stage 1 of 5 (Device Prepare) started...
Apr 19 17:00:12 localhost NetworkManager: <info>  Activation (ttyACM0) Stage 1 of 5 (Device Prepare) complete.
Apr 19 17:00:12 localhost NetworkManager: <info>  (ttyACM0): powering up...
Apr 19 17:00:12 localhost NetworkManager: <info>  Registered on Home network
Apr 19 17:00:12 localhost NetworkManager: <info>  Associated with network: +COPS: 0,2,"12345",0
Apr 19 17:00:14 localhost NetworkManager: <info>  Connected, Woo!
Apr 19 17:00:14 localhost NetworkManager: <info>  Activation (ttyACM0) Stage 2 of 5 (Device Configure) scheduled...
Apr 19 17:00:14 localhost NetworkManager: <info>  Activation (ttyACM0) Stage 2 of 5 (Device Configure) starting...
Apr 19 17:00:14 localhost NetworkManager: <info>  (ttyACM0): device state change: 4 -> 5
Apr 19 17:00:14 localhost NetworkManager: <info>  Starting pppd connection
Apr 19 17:00:14 localhost NetworkManager: <info>  Activation (ttyACM0) Stage 2 of 5 (Device Configure) complete.
Apr 19 17:00:14 localhost pppd[2209]: Plugin /usr/lib/pppd/2.4.4/nm-pppd-plugin.so loaded.
Apr 19 17:00:14 localhost pppd[2209]: pppd 2.4.4 started by root, uid 0
Apr 19 17:00:14 localhost pppd[2209]: Using interface ppp0
Apr 19 17:00:14 localhost pppd[2209]: Connect: ppp0 <--> /dev/ttyACM0
Apr 19 17:00:14 localhost NetworkManager: <info>  (ttyACM0): device state change: 5 -> 6
Apr 19 17:00:14 localhost pppd[2209]: PAP authentication succeeded
Apr 19 17:00:14 localhost NetworkManager: <info>  (ttyACM0): device state change: 6 -> 7
Apr 19 17:00:15 localhost pppd[2209]: LCP terminated by peer
Apr 19 17:00:18 localhost NetworkManager: <info>  (ttyACM0): device state change: 7 -> 9
Apr 19 17:00:18 localhost pppd[2209]: Connection terminated.
Apr 19 17:00:18 localhost NetworkManager: <info>  Marking connection 'Auto Mobile Broadband (GSM) connection' invalid.
Apr 19 17:00:18 localhost NetworkManager: <info>  Activation (ttyACM0) failed.
Apr 19 17:00:18 localhost NetworkManager: <info>  (ttyACM0): device state change: 9 -> 3
Apr 19 17:00:18 localhost NetworkManager: <info>  (ttyACM0): deactivating device (reason: 0).
Apr 19 17:00:18 localhost NetworkManager: nm_system_device_flush_ip4_routes_with_iface: assertion `iface_idx >= 0' failed
Apr 19 17:00:18 localhost NetworkManager: nm_system_device_flush_ip4_addresses_with_iface: assertion `iface_idx >= 0' failed
Apr 19 17:00:19 localhost dbus-daemon: Rejected send message, 2 matched rules; type="error", sender=":1.43" (uid=0 pid=2138 comm="NetworkManager --pid-file=/var/run/NetworkManager/") interface="(unset)" member="(unset)" error name="org.freedesktop.DBus.Error.UnknownMethod" requested_reply=0 destination=":1.44" (uid=0 pid=2209 comm="/usr/sbin/pppd nodetach lock nodefaultroute ttyACM"))
Apr 19 17:00:19 localhost pppd[2209]: Terminating on signal 15
Apr 19 17:00:19 localhost pppd[2209]: Modem hangup
Apr 19 17:00:19 localhost pppd[2209]: Exit.

Hello,

thanks for filling this bug.
You likely notice the line:
localhost pppd[3341]: LCP terminated by peer
LCP means Link Control Protocol. So it looks like the peer is disconnecting.
Maybe a problem with username/password or dial number/APN. Could you please verify this parameters with the one your provider suggest?

Another hint is to change the authentication methods (PPP Settings). Try to disabling some methods. Maybe it's not as useful like the hint above because
pppd[2209]: PAP authentication succeeded seems to work well. But please give it a try. Thank you.

-- 
Fedora Bugzappers volunteer triage team
https://fedoraproject.org/wiki/BugZappers

Thanks for looking into this one and pointing me the obvious which I should have noticed by myself, I added APN name to my phone settings and now NM is able to connect with default settings.

Cheers!