Joel wrote:

No, フォークと would mean you ate with a fork as your dining companion – that is, in the sense of “I ate dinner with a friend”. =P

Though they both use “with” in English, the meaning is different in Japanese. The meaning of the particle で is, as you observed, something closer to “by means of”, but since it’d be downright clunky to use that phrasing in English, it’s normally rendered as “with”.

Arigatou Joel-Senpai :)