How much real difference is there between flours (specifically all-purpose) such as King Arthur, Gold Medal at a considerable savings and a store brand which is even less expensive?
There is a difference beyond just the price.
All-Purpose flours are not the same:
Southerners tend to make more quick breads, pies, cakes, etc. where tenderness is the primary quality factor.
Southern brands of all-purpose flour such as White Lily, Martha White, Red Band, Adluh and others are typically milled from wheat that naturally has a lower gluten percentage. They also blend it to achieve an overall lower percentage. In addition, southern all-purpose flour is usually bleached, often with chlorine gas which weakens the gluten structure of the gluten in it and creates an acidic nature in the dough. Gluten doesn't develop as easily in an acidic environment.
On average, people living in the northeast/midwest tend to bake a lot more yeast-based products (dinner rolls, cinnamon rolls, pumpernickel bread, rye, wheat, white, french bread, etc.) which benefit from a higher gluten percentage.
Northern/Midwest brands such as King Arthur, Hecker's etc. tend to use wheat that has a higher gluten content for the milling of their flour and they typically leave it unbleached which allows the gluten to better develop during mixing/kneading.
National brands such as Gold Medal and Pillsbury are being distributed across the country so they blend their flour to fall within the mid-range of gluten content.
As for store brands, those that are national (such as Kroger/safeway) are probably being milled by the national flour mills and should probably perform about the same. If it's a regional store brand (such as Piggly Wiggly here in the south or Wegman's in the Northeast) I'd be willing to bet that it probably falls within the scope of those regional types of milling practices.
For a chart showing the range of gluten content for various types of flour from cake flour to bread flour (including the all-purpose brands mentioned above) see Flour Power.
These days, there's probably very little difference between Gold Medal and the store brand. They are both industrial products, and may well come from the same mill.
As for the King Arthur, that's a more complex question. Needless to say, their organic product is, well, organic. In the all-purpose department, they will claim that theirs is more nutritious due to their process. I'm in no position to prove or disprove that.
If it's baking you are doing, I would recommend a bake-off and see if you can tell the difference. If you are thickening sauces, heck, buy the store brand. Though, in some cases, a whole-wheat roux has a nice flavor.
My hunch is that the biggest difference you'll find with flour is freshness. If you could find grain milled yesterday (or today!), I bet it would have a much better taste, even if it was from the least expensive brand. So, possibly outside the scope of your question, but, an airtight container for flour is definitely a good idea, as is testing out a grain mill or finding a bakery that has fresh flour, if you're really interested in the secrets of wheat.