гуляли в паркЕ ( If паркЕ than гуляли is correct) шли в парк очень медленно (because there is specifying action очень медленно) ходили в парк (there no specifying actions)

http://www.classes.ru/grammar/127.Rosental-pravopisanie/61.htm §174. Варианты видовых форм п. 8. Необходимо различать значения парных глаголов движения: бегать - бежать летать - лететь водить - вести носить - нести возить - везти плавать - плыть гонять - гнать ползать - ползти ездить - ехать таскать - тащить катать - катить ходить - идти лазить - лезть Первые глаголы в каждой паре обозначают действие без указания на направление или действие, совершающееся не за один прием (глаголы неопределенного движения), а вторые - действия, протекающее в одном направлении, или действие, совершающееся непрерывно и в определенный момент (глаголы определенного движения). Ср.: грузовик возит кирпич - грузовик везет кирпич; самолет летает над лесом - самолет летит над лесом; утки плавают в зарослях камыша - утки плывут к берегу и т.п.

Потому что отрицается действие, его не было вообще.

ходили потому что "гуляли" не сочетается с "в парк" а вместо "шли" было бы "пошли" поскольку завершённое прошедшее время

Вчера было холодно, и мы не шли в парк очень медленно. (шли because this is specifying actions "very slow" ) Вчера было холодно, и мы не ходили в парк. (this is not specifying actions)