В словаре-справочнике Д. Э. Розенталя «Прописная или строчная?» (М., 1989 и др.) дано прямое указание писать названия направлений в военном деле со строчной буквы, например: будапештское направление, курское направление. Такого написания придерживаются научные энциклопедические издания, в том числе военные, и оно вполне закономерно. Направления движения – это не конкретные географические объекты, а ситуативные ориентиры. Прилагательные, указывающие на направления, могут образовываться как от географических названий (обычно имен городов), так и от названий сторон света и других слов, например: донецкое направление, южное направление, юго-западное направление, главное направление. Прилагательные в составе таких сочетаний используются в своем прямом значении.

При этом нельзя не отметить, что в военных документах, например приказах, аналитических записках, сводках, во время Великой Отечественной войны и в настоящее время прилагательные, образованные от географических названий, при слове направление писали и пишут с прописной буквы. Такую орфографическую форму можно признать оправданной прагматической задачей – необходимостью в условиях военных действий быстро ориентироваться в тексте документа. Однако в других сферах, например в СМИ, нужно все же следовать общим орфографическим предписаниям.

Предложение можно построить и так и так.

Можно.

Все слова в этом предложении (кроме пора) – глаголы в неопределенной форме, в том числе и слово поесть. 

Но Ваша догадка отчасти верна. Дело в том, что неопределенная форма глагола (инфинитив) по своему происхождению является застывшей формой имени существительного. Очень красиво об этом сказал известный русский лингвист А. М. Пешковский: «Если бы мы ничего не знали о происхождении неопределенной формы, то мы бы определили ее как "глагол, сделавший один шаг по направлению к существительному". Зная же ее происхождение, мы скажем, что это "существительное, не дошедшее на один шаг до глагола"».

Корректно с запятой: Нам нужно двигаться в направлении, обратном направлению градиента.

Верно с прописной буквы: по Ленинградскому направлению.

Корректен первый вариант.

Правильно: (ехать) в Москву, (уезжать) из Москвы. При указании направления (например, на железнодорожной платформе): на Москву, от Москвы. Вариант с Москвы – за рамками литературного языка.