You could try using newid():
INSERT INTO #RandomUsers
Select TOP 10 userId From Profile WHERE userId <> @UserID
ORDER BY newid()
This way you get ten different users that are not the one you passed in parameter. But I don't know how you can get really good randomness in SQL Server.
Edit:
I think you can also use tablesample() for this kind of issue, but I don't really know how to use this.
By the way, if a hole appears in the id sequence (like user 34 is deleted), you could still pick 34 with your method, while methods taking a sample from the table directly will still work.