Можно ли иметь «лишний» ID в URL REST API?

Даже если пользователи привязаны к магазинам, то раз Вы допускаете возможность использования /users/:userId, предполагаю, идентификаторы пользователей уникальны не только в пределах магазина, но и всей системы. В таком случае, уровень /shops/:shopId будет лишним в задаче изменения информации о пользователе, даже если у пользователя есть привязка к магазину в плоскости бизнес-логики. Поэтому, используйте /users/:userId.

можно.
но если ид юзера достаточно для внесения изменений и эти изменения однозначны - то лучше вариант 1. иначе лучше второй вариант.
пример: меняешь юзеру возраст и надо проверить позволяет ли магазин иметь юзера с таким возрастом или нет (контент 18+). или - при изменении юзера нужны какие то сведения о магазине - то тоже вариант 2 лучше