Can multiple instances of procedure create same #Temp simultaneously?
&quot;I cannot run multiple instance of this procedure simultaneously. Why?&quot;

Could you clarify what you mean by &quot;cannot run&quot;? Do you get an error?
Now, you don't need to check the existence of the table in your stored procedure with the IF OBJECT_ID() thing.
SQL Server will create an instance of the temp table per instance of the stored procedure, and it will only be visible to the creating scope, which is the stored procedure in this case, and to inner scopes, such as if you call another sub-procedure in your code. Once the procedure completes, the temporary table will be gone.
Under the covers, the query processor appends some unique string to the table name in TempDB for each instance.
BOL has all the details: CREATE TABLE (Transact-SQL)
-- In response to OP comment regarding the stored procedure generating the same suffix. --
You are not giving SQL Server enough credit here. If your claim was true, this would have been a major bug; executing multiple instances of a stored procedure which use temp tables is completely supported.
I suspect that you are testing it on a single connection, and seeing that upon re-execution of the same proc, you get the same suffix. This is an optimization for reusing the suffixes for repeated executions from the same session.
What you should test is:
CREATE PROCEDURE P 
AS
BEGIN
CREATE TABLE #T(Col1 INT);
WAITFOR DELAY '00:00:10';
SELECT * FROM TempDB.sys.tables;
END

And then on two or more connection, execute concurrently
EXEC P

Here is what comes up for me:




name




#T_____________000000000004


#T_____________000000000005




HTH