The Vaillant 837 is a superb boiler so clearly this should not be the problem. I fitted a new bathroom with a Mira Excel pumped shower about 12 months ago. Customer was well pleased. Just recently ripped the pump out and fitted a Vaillant combi, The customer is adamant the shower now, without the pump, is far better than before, which frankly surprised me but there you go.
My guess is your problem is you have a poor mains water supply from the street so consequently poor shower performance. Get this checked out.
The boiler should automatically vent any trapped air as it passes through the boiler. Keep an eye on the pressure gauge because as the air escapes the pressure will drop slightly.
Has the toilet now been connected to the high pressure side of the system without a change of ball valve? If it was originally low pressure, the internal workings will have been converted and will now not work correctly.
If normal bleeding does fails to remove trapped air the only remaining solution is to break into the system and remove it manually.
Drain one of the coldest radiators (remove it if it's difficult to gain access to the pipes). Place a short length of hosepipe ( 12 inches) onto one of the valves and place the other end in a large bucket. Open up the radiator valve for 3 - 5 seconds, the rush of water should expel any trapped air. If escaping air is heard, vent until it is clear. Repeat procedure on opposite valve.
Do not let the boiler pressure drop to zero as air may be drawn in.
Once refilled, make sure system is properly balanced.