1. API REST, как правило, именно stateless. То есть каждый вызов API совершенно не зависит от другого.
Таким образом, вся многопоточность остается внутри, а не на вашем REST API
2. Самое большое неудобство для программирования - это блокировки/синхронизации. То есть когда вы используете общие ресурсы, которые не позволяют обращаться к ним конкурентно-параллельно, такие нужно блокировать на время использования. Но эти блокировки, в свою очередь, могут вызвать deadlock.
Блокировать нужно не забывать. Но нужно это делать минимально, только когда нужно. Например, возможно, достаточно будет не exclusive lock, а всего лишь rw-lock на read.
3. Реализовать проще на том, что лучше знаешь. Я бы выбрал Go, но это я. Реализовывать нужно на том, что лучше знаешь лично ты.