Paenibacillus polymyxa can produce the (R,R)-stereoisomer of 2,3-butanediol (2,3-BDL) which is industrially very useful. Two important factors affecting (R,R)-BDL production by P. polymyxa ATCC 12321, medium composition, and addition of acetic acid to the culture were investigated in this study with accompanying comparative proteomic analysis. For this purpose, a simple control strategy of O2 supply was applied on the basis of an optimized basal medium: after a short period of batch cultivation with relatively high O2 supply, the culture is switched into strong O2 limitation, thereby promoting BDL formation. Three parallel fed-batch cultures starting from the same batch culture in an early stationary phase were then comparatively studied: the first one was running as control with the only change of O2 supply; the second was, in addition, supplemented with 0.5 g/L yeast extract; and the third one was further added with 6 g/L acetate. Proteomic analyses of the three fed-batch cultures identified more than 86 proteins involved primarily in the central carbon metabolism, amino acid biosynthesis, energy metabolism, and stress responses. The examination of expression patterns of selected proteins, especially combined with fermentation data, gave valuable insights into the metabolic regulation of P. polymyxa under the different given conditions. Based on the proteomic analysis and further medium optimization studies, methionine was identified as one major growth-limiting factor in the basal medium and explains well the effect of yeast extract. Acetic acid was found to trigger the so far less studied acetone biosynthesis pathway in this organism. The latter is suggested in turn to enhance the switch from acidogenesis to solventogenesis. Thus, these findings extended our knowledge about BDL formation in P. polymyxa and provided useful information for further strain and process optimization.