Не пойму как переводится предложение

О-о, вас еще не раз будут ставить в тупик всякие странные выражения на английском :-). С моей дилетантской точки зрения, таковых непомерно много.
Вот в словаре (кстати, далеко не самом объемном) глагол to go имеет 34(!) значения. Есть среди них и то, что соответствует вашему случаю:
- подходить, подойти, быть под стать (чему-либо)
the blue scarf goes well with your blouse - этот голубой шарф хорошо подходит к вашей блузке

По аналогии с этим примером смотрим вашу фразу. Если бы она выглядела так: I bought a pair of red shoes that GOES with my new dress, мы бы перевели "...которые подходят к моему новому платью"

Но поскольку у вас стоит неопределенная форма глагола - to go, то она, видимо, отражает намерение, перспективу, чему как раз соответствует перевод Миши Еременчука.

К новому платью я купила красные туфли, хорошо сочетающиеся с ним по цвету.

Миша Еременчук прав!

Это предложение не переводится дословно, переведите его так: " Я купила
пару красных туфель, которые подходят к моему новому платью".

которые подойдут к

Я купила пару красных туфлей К своему платью.
Они могут не подходить ни в каком разумном смысле, она их купила в, хм, пару к платью. to go with здесь означает парность, ансамблевость. Это может быть сочетаемость, может быть гармоничность, а может просто по минутному порыву души.

Подходящих моему новому платью

Я купил пару красных башмаках, чтобы пойти с моим новым платьем - это гугл перевел, может имеется ввиду, что они подходят платью

Может подойдут ?