Bieniuk to jeden z najbardziej znanych graczy Lechii, do której trafił z Ogniwa Sopot. Piłkarskiego fachu uczył się od Józefa Gładysza – wychowawcy młodzieży w gdańskim klubie. Z racji wzrostu nosił pseudonim „Palmer” – od nazwiska angielskiego gracza, Carltona Palmera. W pierwszej drużynie Biało-Zielonych zadebiutował jako 17-latek, w sezonie 1996/1997. Gdańszczanie występowali wówczas w niższych ligach. Na wyróżniającego się defensora uwagę zwróciła Amica, do której trafił w 1998 roku. Z tym klubem sięgnął po krajowe laury i jako zawodnik „Kuchennych” zadebiutował w reprezentacji. 14 lutego 2003 roku kadra Pawła Janasa wygrała towarzysko z Macedonią (3:0) na stadionie Poljud w Splicie. Biało-czerwoni wystąpili w ligowym składzie. „Palmer” zagrał w 1. połowie u boku Jacka Zielińskiego. Na boisku pojawili się jeszcze m.in. Grzegorz Szamotulski, Rafał Lasocki, Andrzej Niedzielan czy Grzegorz Rasiak.

Bieniuk nie zrobił wielkiej kariery w biało-czerwonych barwach. Z 8 spotkań aż 7 miało charakter towarzyski. Zdobył jedną bramkę – z Maltą (4:0) w Ta’Qali pod koniec 2003 r.

Ten jedyny mecz o punkty, był zarazem jego pożegnaniem z drużyną narodową. „Palmer” zagrał w niej po ponad 4-letniej przerwie – już jako zawodnik Widzewa (pozostałe spotkania rozegrał jako piłkarz Amiki). 14 października 2009 roku biało-czerwoni kończyli nieudane kwalifikacje do mundialu w RPA. W zimowej scenerii, na świecącym pustkami Stadionie Śląskim, Polacy przegrali ze Słowacją (0:1) po samobójczym golu Seweryna Gancarczyka. Nasz zespół prowadził tymczasowy selekcjoner – Stefan Majewski. W polskim zespole zagrali m.in.: Jerzy Dudek, Jakub Rzeźniczak, Roger Gurreiro czy Ireneusz Jeleń.

Niemal całą karierę Bieniuk spędził w Polsce. Z kraju wyjechał w 2006 roku do tureckiego Antalyasporu. Po dwóch latach rozwiązał kontrakt i podpisał umowę z Omonią Nikozja. Ale na Cyprze nie zagrał, gdyż z powodu nieudanych testów medycznych klub postanowił się z nim rozstać.

W lutym 2009 roku „Palmer” wrócił do Polski. Najpierw występował w Widzewie (przez 2,5 roku). A na koniec kariery wrócił do Lechii Gdańsk. Buty na kołku zawiesił po sezonie 2013/2014. Potem został dyrektorem sportowym. Szefował m.in. Akademii Lechii. Później został asystentem trenera Piotra Stokowca. Był nim również u kolejnego szkoleniowca – Tomasza Kaczmarka.

W październiku 2021 roku Bieniuk zrezygnował z tej funkcji. A potem definitywnie rozstał się z Lechią. W marcu 2022 r. został ekspertem TVP Sport.

► Puchar Polski z Amiką Wronki - jako piłkarz (1999, 2000) i Lechią Gdańsk – jako II trener (2019)
► Superpuchar Polski z Lechią  – jako II trener (2019)
► 3. miejsce w ekstraklasie z Amiką – jako piłkarz (2002) i Lechią – jako II trener (2019)