Она ушла в булочную, а Степан с остальными уже пришел(ли) в спортзал.
...а так как он с товарищами наконец-то замолчал(ли), то то-то и то-то...
1) Общее решение по правилу Розенталю выглядит так:
Форма мн. числа сказуемого показывает, что в роли подлежащего выступает все сочетание, т.е. действие приписывается двум взаимосвязанным равноправным субъектам.
Форма ед. числа сказуемого показывает, что подлежащим является только сущ. в И. падеже, а сущ. в Т.падеже выступает в роли дополнения, обозначая сопутствующее лицо.
http://www.evartist.narod.ru/text1/64.htm#з_04
2) Для каждого предложения нужно определить равноправность действующих лиц по ситуации.
3) Она ушла в булочную, а Степан с друзьями уже пришел в спортзал.
Здесь главные действующие лица — это она и Степан, а друзья относятся к второстепенным персонажам.
Сравнить: Она ушла в булочную, а Степан и все остальные уже пришли в спортзал. Так будет выглядеть предложение, когда рассматриваются равноправные действия всей компании.
4) ...а так как он и его товарищи наконец-то замолчали...
Для этого предложения конструкция он с товарищами не подходит, так как участие в этом действии всех субъектов мыслится как равноправное (а в этом случае нужно употребить местоимение они).
Сравнить (неравноправное действие):
В 2000 году он с друзьями решил немного погонять по Скандинавии...
Подле него была дочь одного персидского хана, которую он с братом похитил из родительского дома...
— Степан пришёл не один. — С кем пришёл Степан? — Степан пришёл с остальными ребятами. — Ясно. Значит, Степан и остальные уже пришли в спортзал.
Я бы сказал пришёл. Но пришли, если с "и" (и остальные):
Она ушла в булочную, а Степан и остальные уже пришли в спортзал.
Задумался, что будет, если заменить остальных на условного Васю. И с ним я бы уже сказал пришли. Так что немного сам запутался. :(
Что касается второго предложения, в случае местоимения он я уверенно скажу в единственном числе (замолчал), а если поставить того же Степана или другое имя, то считаю, что ситуация та же, что и в первом предложении. То есть я предпочёл бы единственное число.