I installed a 58T chainring for a small improvement. I can pedal up to 40km/h with reasonable comfort. Since the Birdy is my commuting/touring bike, that's adequate.
Jur, either you spin slowly or your cyclocomputer is set incorrectly. At 100 RPM you should get 42km/h out of the stock 56T chainring and the 11T cog. I've only lacked gears on steep descents.