There is no border between Kazakhstan and Mongolia. No matter how close they might look on a map, reality is that they don't have a common border.
There are several border crossings between China and Mongolia but NONE currently are open to international travelers on a regular basis. Very rare reports suggest that sometimes a foreigner on a tour can cross here, but most reports are that international travelers get turned back far from the border as on both sides they are military zones.
There are multiple reports on the internet that the Bulgan (Mongolia/China) border crossing (Khovd Province in Mongolian Altai) is an international crossing. This is NOT true. It appears to be open to locals only or Chinese and Mongolian tourists. Bulgan border crossing
Only option between China and Mongolia is the crossing at Dzamyn Ude to Erlian (Erenhot). You don't need to go to Beijing. There are trains that cross the border and go to Hohhot.
Ruth