Is foot plural here because "we" is plural?
No, it is always kwenda kwa miguu, independent on the number of people in the subject. This makes actually sense, because most people you both their feet to walk:). It the English expression that is a bit illogical here!
Its always on foot in English and we use use with forms of transport