Скончыў Беларускую акадэмію мастацтваў у 1998 годзе, затым аспірантуру, падчас вучобы атрымліваў стыпендыю адмысловага фонду Прэзідэнта Рэспублікі Беларусь па падтрымцы таленавітай моладзі, якая мае творчыя дасягненні. Андрэй Кудзіненка — адзін з апошніх вучняў легенды «Беларусьфільма» Віктара Турава. Пасля сканчэння Акадэміі здымаў кароткаметражныя фільмы, рэкламу. У 2002 годзе Кудзіненка зняў поўнаметражны дэбют «Битва пяти воинств» (бел.: «Бітва пяці воінстваў»).
Зняў фільм «Акупацыя. Містэрыі» (2004). Істужку, якая апавядае пра жыццё ў акупаванай нацыстамі Заходняй Беларусі, запрасілі ў афіцыйную праграму Ратэрдамскага міжнароднага кінафэсту. Услед за гэтым «Акупацыю» паказалі ў паралельнай праграме Маскоўскага міжнароднага кінафестывалю. У Беларусі фільм быў забаронены да паказу Міністэрствам культуры Беларусі. Кудзіненка паехаў у Расію, дзе ўдзельнічаў у шэрагу праектаў, папрацаваў у камандзе Паўла Лунгіна. У 2009 годзе рэжысёр атрымаў запрашэнне «Беларусьфільма», а на пачатку 2010 года Міністэрства культуры вярнула фільм «Акупацыя. Містэрыі» ў адзіны дзяржаўны рэгістр, і 15 лютага 2010 года адбылася беларуская прэм’ера фільма.
На кінастудыі «Беларусьфільма» Андрэй Кудзіненка пачынаў працу над «Масакрай», гэты фільм сам рэжысёр акрэсліў як сінтэз містычнага трылера, меладрамы і эротыкі[1]. Сюжэт «Масакры» (сцэнарыст Аляксандр Качан) грунтуецца на навеле Праспера Мерымэ пра мядзведзя-пярэваратня («Локіс») і па матывах старажытных беларускіх легенд.
Уладальнік прыза «За найлепшы дэбют» на фестывалі «Літаратура і кіно» (Гатчына, Расія), «За найлепшы эксперыментальны фільм» на MediaWave’ 99 (Венгрыя).
У кастрычніку 2012 і 2014 гадоў выступіў членам журы кінафестывалю беларускага кіно, які праходзіў у Варшаве (Польшча). З 2015 года куратар мультымедыйнага праекту «Хронотопь».
