Amica Wronki

Przed sezonem 1998/1999 przeniósł się do Amiki Wronki. W polskiej ekstraklasie debiutował 22 maja 1999 w spotkaniu Amiki Wronki z Polonią Warszawa, zakończonym zwycięstwem wronczan 1:0. Wywalczył też z Amiką Puchar Polski w piłce nożnej (1998/1999).).

W sezonie 1999/2000 stał się podstawowym graczem drużyny. Zagrał w niej 21 meczów ligowych (6. miejsce w Ekstraklasie) oraz zdobył kolejny Puchar Polski (w finale Amica pokonała w dwumeczu Wisłę Kraków – 2:2 i 3:0).

W sezonie 2000/2001 strzelił swoją pierwszą bramkę w Ekstraklasie, w trakcie meczu Amica Wronki–GKS Katowice, rozegranego 19 sierpnia 2000 i zakończonego remisem 1:1. W kolejnym sezonie zajął z Amiką 3. miejsce w lidze (zagrał w 24 meczach ligowych i strzelił 3 bramki). Dotarł też do finału Pucharu Polski, gdzie Amica uległa w dwumeczu Wiśle Kraków (2:4, 0:4). Bieniuk zagrał tylko w pierwszym spotkaniu.

W sezonie 2001/2002 Amica wystąpiła w rozgrywkach Pucharu UEFA. W rundzie wstępnej wyeliminowała walijski Llansantffraid FC (5:0, 7:2), a jedną z bramek strzelił Bieniuk. W I rundzie Amica pokonała w dwumeczu szwajcarski zespół Servette FC (3:2, 1:2). W kolejnej fazie wroniecka drużyna zmierzyła się z hiszpańską Málagą. Odpadła po dwóch porażkach 1:2.

W sezonie 2003/2004 Amica ponownie zajęła 3. miejsce w Ekstraklasie. Bieniuk zagrał w 15 meczach ligowych i strzelił dwie bramki.

Kolejny rok przyniósł zespołowi ponowny występ w Pucharze UEFA. Po wyeliminowaniu w I rundzie eliminacyjnej węgierskiego zespołu Kispest Honved Budapeszt rywalem Amiki w I rundzie został łotewski FK Ventspils. Dwumecz zakończył się wynikami 1:1 i 1:0. Bieniuk zagrał w obu spotkaniach. W ten sposób Amica wywalczyła historyczny awans do fazy grupowej Pucharu UEFA.

W grupie F Amica zajęła ostatnie miejsce, przegrywając wszystkie spotkania – 0:5 ze szkockim Rangers FC, 1:3 z austriackim Grazerem AK, 1:3 z holenderskim AZ Alkmaar i 1:5 z francuskim AJ Auxerre. Bieniuk zagrał we wszystkich meczach.

Antalyaspor

Po sezonie 2005/2006 opuścił Amikę i podpisał trzyletni kontrakt z klubem tureckiej Superligi Antalyaspor Kulübü. Pierwszą bramkę dla nowego zespołu zdobył 9 września 2006 w meczu z Fenerbahçe SK (2:4). Już w pierwszym sezonie gry Bieniuk spadł z zespołem z Süper Lig do niższej klasy rozgrywkowej. W kolejnym roku awansował z Antalyasporem do Süper Lig. W sezonie 2008/09 zagrał tylko w 2 spotkaniach i strzelił 1 bramkę. Łącznie w barwach tureckiego klubu zagrał w 53 meczach, strzelając w tym czasie trzy bramki. W 2008 rozwiązał kontrakt z klubem, a pod koniec roku związał się umową z cypryjską Omonią Nikozja. Po niezbyt udanych testach medycznych rozwiązano kontrakt.

Widzew Łódź

11 lutego 2009 podpisał kontrakt z pierwszoligowym Widzewem Łódź. Zadebiutował w nim 14 marca 2009 w spotkaniu z Koroną Kielce (2:2). Z łódzkim klubem zajął 1. miejsce w lidze i awansował do Ekstraklasy, lecz z powodu decyzji PZPN w związku z aferą korupcyjną Widzew musiał kolejny sezon rozegrać ponownie w I lidze. Rok później Widzew znów awansował do najwyższej klasy rozgrywek w Polsce.

21 sierpnia 2010 zadebiutował w barwach Widzewa w Ekstraklasie w meczu z Wisłą Kraków (0:1). Na pierwszą bramkę dla Widzewa Bieniuk czekał aż do 28 sierpnia 2011, gdy pokonał Mariána Kelemena w spotkaniu ze Śląskiem Wrocław (2:1).

Powrót do Lechii

9 lipca 2012 rozwiązał za porozumieniem stron kontrakt z Widzewem i związał się z Lechią Gdańsk, z którą podpisał dwuletni kontrakt z możliwością przedłużenia o kolejny rok. W Ekstraklasie zadebiutował w meczu z Pogonią Szczecin.

Przed sezonem 2013/2014 został nowym kapitanem zespołu. 30 lipca 2013 w meczu towarzyskim przeciwko FC Barcelonie strzelił gola na 1:0.

Po sezonie 2013/2014 zakończył karierę piłkarską. 29 października 2014 powrócił do Lechii jako dyrektor sportowy.