Which user's password does `sudo` asks for?

1. In its most common configuration, sudo asks for the password of the user running sudo (as you say, the user corresponding to the process’ real user id). The point of sudo is to grant extra privileges to specific users (as determined by the configuration in sudoers), without those users having to provide any other authentication than their own. However, sudo does check that the user running sudo really is who they claim to be, and it does that by asking for their password (or whatever authentication mechanism is set up for sudo, usually using PAM — so this could involve a fingerprint, or two-factor authentication etc.).

   sudo doesn’t necessarily grant the right to become root, it can grant a variety of privileges. Any user allowed to become root by sudoers can do so using only their own authentication; but a user not allowed to, can’t (at least, not by using sudo). This isn’t enforced by Linux itself, but by sudo (and its authentication setup).

2. sudo does indeed ask for the password after it’s started running; it can’t do otherwise (i.e. it can’t do anything before it starts running). The point of sudo asking for the password, even though it’s root, is to verify the running user’s identity (in its typical configuration).

sudo usually asks for the password of the user running it, though this can be configured:

Unlike su(1), when sudoers requires authentication, it validates the invoking user's credentials, not the target user's (or root's) credentials. This can be changed via the rootpw, targetpw and runaspw flags, described later.

Setting rootpw has sudo always ask for root's password, targetpw asks for the password of the user sudo will eventually run the program as, and runaspw asks for the password of the user set in runas_default.

A sudo binary set up like that can indeed be started with root privilege by any user. Assuming sudo doesn't have any bugs with its authentication code, that in itself won't matter much.

Somewhat similarly, any process can also execute code in kernel mode, by calling any system call, say open(). (that's not the same as userspace code as root.) As long as the kernel doesn't have bugs, they won't be able to run arbitrary code, though.

From the first line(s) of man sudo:

DESCRIPTION
sudo allows a permitted user to execute a command as the superuser or another user, as specified by the security policy. The invoking user's real (not effective) user ID is used to determine the user name with which to query the security policy.

So:

1. The invoking user's real (not effective) user ID is used ...

2. Yes, any (permitted) user can gain the superuser (or other) additional privilege(s) by running sudo and then providing the (configured) authentication required. Both permitted and configured are set in sudoers file(s).

3. Can Linux restrict that on some users?
   Yes, it can, but it doesn't. Linux is set to allow the sudo binary to make the decision based on the set of rules (security policy) inside the sudo program and inside the file /etc/sudoers. Usually, other files (also/instead) may be used.

From man setresuid:

DESCRIPTION
setresuid() sets the real user ID, the effective user ID, and the saved set-user-ID of the calling process.

4. The only way to gain superuser permissions granted by the kernel is to run a program suid. It can not be otherwise. It is the way Linux has selected to grant superuser permissions.

5. After the kernel has loaded an executable that can not be modified by any other user (file and directory owned by root and writable only by root) the executable itself (sudo) authenticates the user by asking for its password (or something else as configured) and decides if and which permissions to grant.