I haven't personally looked at CarbonToolbar, but just as a guess, are there any other resources (e.g. pictures that go in the toolbar)? Those can add up pretty fast. Why don't you look in the bundle and see what's so large?
Also, did you try turning on optimization to -O3? It's not usually as large an improvement as turning off debug symbols, but it can help sometimes.