Players on our server have permission to use portals, the plugin is working fine. However, with NoCheatPlus, players are kicked for walking through a portal that leads to a world they don't have access to. This is quite annoying for our new players who don't have access to every world.

Unfortunately, there's nothing we can do for you. NoCheatPlus should be able to recognize that the teleport was triggered by a plugin and therefore the players aren't cheating.