Бидерман выиграл 200-метровку вольным стилем на европейском первенстве в 50 метровом бассейне 2008 года, финишировав первым с результатом 1:46,59. Показав время 3:47,69 на четырёхсотметровке вольным стилем и 1:46,37 (национальный рекорд) на дистанции вдвое короче, Бидерман смог отобраться на Олимпийские игры 2008 в Пекине, где стал пятым (1:46,00) в финале на 200 метрах м и 17-м (3:48,03) на дистанции в 400 метров, не попав в финал.
26 июля 2009 года на чемпионате мира в Риме Бидерман выиграл финал на четырёхсотметровой дистанции, показав время 3:40,07, что более чем на 7 секунд выше его предыдущего личного достижения и на одну сотую лучше предыдущего мирового рекорда Яна Торпа, установленного в 2002 году. Через два дня, 28 июля, он выиграл с результатом в 1:42,00 вторую золотую медаль на двухсотметровке, победив при этом американского пловца Майкла Фелпса и побив его же мировой рекорд. Во время заплывов на Бидермане был полиуретановый комбинезон, который был запрещён с 1 января 2010 года. На том же первенстве мира немецкой команде, в составе которой плыл Бидерман, досталось серебро в комбинированной эстафете.
В 2009 году Пауль был признан лучшим пловцом года в Европе (первый немец, выигравший эту награду с 1986 года) и лучшим спортсменом Германии.