When exactly are multiple users unable to simultaneously run a stored procedure with a temp table?

This applies to local temp tables.

The difference between named and unnamed constraints is this:

CREATE TABLE #t1 (c1 INT PRIMARY KEY CLUSTERED)

CREATE TABLE #t2 (c1 INT,
                     CONSTRAINT pk_c1 PRIMARY KEY  CLUSTERED(c1) )

Letting the system name constraints makes it extremely unlikely that there will be a collision. In this example, if you open two windows in SSMS, you'll be able to create #t1 in both, but not #t2.

Global temporary tables are shared by all users, so you have to handle things differently. They don't get 'destroyed' until the last session is done using them, so you need to make sure that when users access them, they can only access their data. This is sometimes done by SPID, other times by a hash value. It depends on how the global temp table is used.

Typically for global temp tables, stored procedures will check to see if they exist, and then only create them if the OBJECT_ID() is NULL.

Multiple users means multiple sessions. The login name has nothing to do with it. If George runs sp_something @i = 1 and Gina runs sp_something @i = 2, it doesn't matter if they're both logged in as User1, they'll have different SPIDs.

I think of it as you can't have any duplicate names in tempdb.sys.key_constraints. Here's what's in that metadata view on one of my servers:

All of the odd names that end with _6E... were names generated automatically by SQL Server. They are not named constraints because I did not explicitly give them a name when creating them. SQL Server generates a constraint name behind the scenes that in theory avoids name collisions.

If I try to create the following table in two different sessions:

create table #x1 (
ID INT NOT NULL,
CONSTRAINT NAMED_CONSTRAINT_1 PRIMARY KEY (ID)
);

The one that runs second throws an error:

Msg 2714, Level 16, State 5, Line 1

There is already an object named 'NAMED_CONSTRAINT_1' in the database.

Msg 1750, Level 16, State 1, Line 1

Could not create constraint or index. See previous errors.

Checking out the view again:

If I try to create the following table in two sessions there's no issue:

create table #y1 (
ID INT NOT NULL,
PRIMARY KEY (ID)
);

Here's the metadata view:

Just to answer your questions directly: the part that you quoted applies to both local and global temporary tables, a named constraint is one in which you deliberately give it a name, and multiple users means multiple sessions.