Sudo user with restricted rights

I'm trying to create user with restricted sudo privileges. These users should be able to do everything except create new users. Do I edit this in the sudoers file directly and if yes, how do I implement this restriction?

IMO impossible: If I can open f.e. a roots shell I can create users - the allowed task (opening a shell) would be a workaround for the unwanted. Such tools are made to allow special tasks - not to deny one.
maybe have a look at doas(1), which comes with MUCH less cruft and dependencies (none) and has a far easier to read and understand (i.e. less error prone) config syntax

Also, it is generally a better idea to allow specific commands instead of trying to prevent misuse by blacklisting commands. However, doas.conf(5) also knows 'deny' rules. e.g.
permit myuser
deny myuser adduser

This wouldn't prevent myuser from editing the doas.conf or just becoming root and then add users though, so again: only whitelist what should be explicitly allowed, everything else is an illusion of security.
How do you create a new user? There are several ways to do it. You can run the adduser command. There are probably GUI-based applications that accomplish the same thing. You can modify /etc/passwd and related files with the vipw command, which edits them in place. And if you know you're doing, you can accomplish the same thing with command-line utillities, like cat / mv / sed and so on. So saying "to do everything except create new users" makes no sense.

I think the correct answer to this problem is not technical, but organizational: Make sure the person you trust with sudo is actually trustworthy, and then instruct them correctly. If that doesn't work:

In addition to the doas suggestion, how about the following: Instead of excluding one particular task, make a list of what tasks are included. Then for each of them, create a way to do it that does NOT require using a shell. One example is to create a variety of shells scripts, one per task, and allow each of them individually.

In addition, I also prefer doas over sudo. Easier to configure and simpler.
One word of warning, be careful allowing commands like vi(1) or less(1) with sudo(8) (or doas(1)). Both vi(1) and less(1) have the possibility to execute a shell command, which would allow someone to spawn a shell with root access. There are a number of 'gotchas' to watch out for.
And even if you are not allowing user to have those tools he may craft them himself. There are really many ways of doing all that (jail escape in general, not to be confused with FreeBSD jails). You want user to have all but user creation. RBAC is really tool for this. So here MAC could help.

Funny sidenote: maybe you could use chflags feature on master.passwd. If he's new enough he may not be able to "crack" that.
IMO impossible: If I can open f.e. a roots shell I can create users […]
I second that. If the user has physical access to a machine, they are virtually root users.
[…] These users should be able to do everything except create new users. […]

You could at least separate user management from system management: All users must authenticate against a (remote) Kerberos or LDAP directory instance. Thus a user granted root privileges can still wreak havoc on his personal machine – including creating local users – but it does not affect other workstations.​