Neither and nor with is necessarily colloquial in such examples; they are equally suitable in more formal registers as well.
There is not necessarily a difference between having, for example, a burger and fries or burger with fries, but oftentimes, using and indicates that the components are of equal significance— you would not have one without the other. Using with suggests the object of with is secondary, and optional or replaceable.
Having chips and salsa indicates that the chips and the salsa are of comparable importance— you would not eat one without the other. If you have chips with salsa, on the other hand, you indicate that the chips are the main item of interest, and the salsa is an accessory to it. You would have eaten the chips without salsa, either plain or perhaps with queso or guacamole or another dip.
Additionally, and to address your second question, a great many food-related pairs in English are formed as irreversible binomials with and. Many are combinations which are so common they have become idiomatic, like toast and jam or ham and eggs, and refer to a single dish or other common pairing that combines those components.
There are at least dozens of these. Some common US examples include
- biscuits and gravy
- black beans and rice
- bread and butter
- cheese and crackers
- chicken and dumplings
- chicken and waffles
- cream and sugar
- fish and chips
- ketchup and mustard
- lemon and lime
- peanut butter and jelly
- peaches and cream
- pork and beans
- salt and pepper
- salt and vinegar
- sausage and peppers
- soup and [a] sandwich
- spaghetti and meatballs
- steak and cheese
- steak and eggs
- surf and turf
- wine and cheese
- wings and beer
(many of these are familiar around the world, along with bangers and mash, but Yanks say bacon and eggs whereas Brits say eggs and bacon).
In such cases, the name of the dish should be treated as a whole, singular unit, and there is nothing unusual about coupling them with other foods using and. For example, it was not difficult to find recent news articles with macaroni and cheese and:
Net sales in the U.S. segment of the business alone were up 8.5% for the company that sells macaroni and cheese and Heinz ketchup. Stephanie Ritenbaugh, Pittsburg Post-Gazette
Luby’s currently sells some of its most iconic dishes in frozen food aisles at H-E-B stores: macaroni and cheese and fried fish. Eric Webb, Austin American-Statesman (via The Dallas Morning News)
Macaroni and cheese and frozen meals generated the biggest sales gains among Kraft Heinz's top five product categories. Tara Lachapelle, Bloomberg
Mike McMurphy will be serving gourmet grilled cheese sandwiches, macaroni and cheese and homemade soups out of his “Cheese It Up” food truck. Lee Belote, The Virginian-Pilot
Breaking the phrase apart would change the meaning. Macaroni, cheese, and frozen meals has three distinct items: [macaroni], [cheese], and [frozen meals]. On the other hand, macaroni and cheese and frozen meals has two: [macaroni and cheese] and [frozen meals]. And you could say macaroni with cheese, but this suggests something special and different from the familiar dish of macaroni and cheese.
This also applies in literary expressions where the combination is metaphorical rather than literal, like apples and oranges or milk and honey. For this reason, I would not answer meat and potatoes if someone asked me what I had eaten, even if I had, in fact, eaten both meat and potatoes. It is an expression meaning something conventional, basic, or fundamental. Additionally, as most Americans have some kind of animal protein with every dinner, one would at least specify the type of meat—beef, lamb, pork, etc.