Да, это возможно.
SQL Server справится с этим нормально - это то, что делают базы данных, обрабатывают несколько соединений одновременно.
Я не знаю, что вы подразумеваете под «множественным экземпляром хранимой процедуры» - в базе данных есть только одно определение SP, и оно будет выполнено. Это может быть выполнено многими потоками при необходимости. База данных будет обрабатывать параллелизм для вас.
Использование блокировок зависит от приложения и способа доступа к базе данных (и означает действий, которые вы выполняете - должны ли они быть атомарными / сериализуемыми и т. Д.).