Had the same problem, and the very same SIM worked instantly with my Phone.
NAT was enabled by default but manual APN (it was "internet.t-mobile" for me) solved it.
My provider (congstar) has a hard-to-find manual mobile connection site (at
https://forum.congstar.de/thread/46325-mobil-surfen-mit-congstar-manuelle-einstellungen-zum-mobilen-internet-apn/ ), where he supplied all the information such as Auth-Protocol to be used (CHAP for me) and password etc.
Check which one you need, I did not need the standard data, but the one specified for routers.
Note: username "tm" and password "tm" seems so trivial, some devices may get them as updates from their maintainers (such as my google phone), but teltonika may not be up-to-date here, so manual is required?