primary key нужен всегда.
Если по логике вашего приложения одному user_id может соответствовать только один пользователь в каждом service_id - то PK на первые два поля.
Если несколько - то pk на 3 поля.
Порядок полей при указании PK таблицы связей важен. Для mysql/innodb очень важен, т.к. таблица кластеризована по PK и любое обращение по вторичному ключу влечёт поиск по PK (кроме покрывающих индексов). Порядок выбирайте исходя из наиболее частых запросов к таблице, чтобы максимум запросов могло идти по первичному ключу.