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.