GREAT meat to find at veeakker. They are situated in Leuven but have other places they deliver to. Service is great, the beef/lamb/fish (e.g. wild alaska salmon) couldn't be higher quality. The prices can be high but you can always supplement your diet with organic, cheaper meat. Maybe even horse meat.
You can go to the BioPlanet to find practically everything you'd need, except for grass-fed stuff and probably bones too.
If you live near Grimbergen there is the "Groentehof" that have GREAT vegetables and fruits (this store closed because the owners retired, but they still sell apples).
And for supplements, I just use iHerb.
To be honest, I never go to any supermarket. Just the butcher and vegetables at the organic store.
I get oysters from crown prince on iHerb. Some supermarkets (eg. Delhaize) also carry organic fruit and Haagen-Dazs (okay not that paleo but it comes close). Oysters can also be found in the Delhaize but it's crazy expensive and you have to open the shells yourself which broke 4 of my knives :).