В обоих случаях ставится запятая.

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

Глагол подходить в значении "оказаться соответствующим кому-, чему-л., годным для кого-, чего-л." не требует предлога, например: это платье подходит маме. Поэтому верно: Подходим идеально мы друг другу.

В современном русском языке в слове надежда приставка уже не выделяется. «Морфемно-орфографический словарь» А. Н. Тихонова предлагает такой вариант разбора: надежд-а. Исторически – да, это слово образовано от nadeti 'положить, поставить' – префиксального производного от *deti > деть  'класть, ставить'. Надежда буквально – 'то, на что полагаются'. Но это, подчеркиваем, исторический состав слова; при синхронном (современном) морфемном анализе выделение приставки на- и суффикса -жд- нецелесообразно.

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

Возникновение переносного значения идет в значении 'хорошо выглядит на ком-то' можно объяснить похожим процессом, произошедшим с глаголом подходить: из значения приближения развилось метафорическое значение 'гармонично выглядеть, соответствовать'. Глагол в переносном значении, как и в исходном, употреблялся с предлогом к, который относительно быстро был в этом значении утрачен. Скажем, в «Извлечениях из учебника "Начертание ествественной истории"» В. Ф. Зуева (1785) читаем: «Зверями называются такие животные, кои строением своего тела, черевами и органами чувств наиболее подходят к человеку» (то есть максимально близки). Из идеи пространственной близости и возникает метафорическое значение соответствия.

Вопрос непростой. Если подходить к ответу исключительно формально, то следует рекомендовать не ставить тире, поскольку между подлежащим пословица и сказуемым-существительным помощница стоит дополнение всем делам. Вместе с тем этот случай отличается от иллюстрирующего правило примера Мой отец для меня друг и наставник (см. пункт 6 параграфа 15 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина). В примере из справочника дополнение для меня стоит действительно между подлежащим и сказуемым, оно не связано тесно ни с тем, ни с другим; по сути это субъектный детерминант, обычная позиция которого — начало предложения, сравним: Для меня мой отец — друг и наставник. В приведенном Вами примере такое перемещение дополнения всем делам невозможно, поскольку оно связано только со сказуемым помощница, образуя с ним словосочетание. Если учесть этот факт, поставить тире вполне уместно: Пословица — всем делам помощница.