Тренер: Алексей Олейник
Активно заниматься единоборствами начал в возрасте девятнадцати лет, долгое время тренировался вместе со своим старшим двоюродным братом Алексеем Олейником, который на тот момент был уже известным во всём мире бойцом. В молодости неоднократно участвовал в соревнованиях по грэпплингу, панкратиону, боевому самбо. Является победителем международного турнира по боевому самбо среди клубных команд в Киеве, победителем международного турнира по боевому самбо памяти Г. П. Долголенко, чемпионом Москвы по боевому самбо, дважды побеждал на этапах Кубка Содружества Наций — имеет звание мастера спорта по боевому самбо.
Со временем получил чёрный пояс по бразильскому джиу-джитсу. Начиная с 2008 года выступает в профессиональном ММА, преимущественно на территории России.
Участвовал в серии отборочных турниров M-1 Challenge, победив всех четырёх своих соперников, и позже несколько раз выступал на турнирах организации ProFC. Дрался довольно часто, так, в одном только 2009 году провёл десять профессиональных боёв.
В феврале 2012 года провёл один из самых известных своих поединков, встретившись в Ирландии с исландцем Гуннаром Нельсоном и проиграв ему рычагом локтя в первом же раунде. В период 2012—2014 годов Бутенко активно выступал в местном харьковском промоушене «Оплот», созданном при одноимённом клубе при участии его брата Алексея Олейника. Здесь он выходил в клетку ещё чаще, в частности в 2013 году 14 раз — победил почти во всех случаях, хотя уровень оппозиции был не очень высок. Тогда же на международном турнире «Кубок чемпионов» в Новосибирске состоялся другой памятный его поединок, когда он раздельным решением судей уступил россиянину Александру Сарнавскому.
С 2014 года после расформирования «Оплота» переехал на постоянное жительство в Колпино и начал выступать за местный бойцовский клуб FightSpirit. В это же время подписал контракт с M-1 Global, победил здесь среди прочих опытного финна Нико Пухакку. Провёл один поединок в промоушене Fight Nights, тем не менее, бой против Динислама Камавова закончился ничьей. Благодаря череде удачных выступлений удостоился права оспорить титул чемпиона M-1 Challenge в лёгком весе, который стал вакантным после того как действующий чемпион Мансур Барнауи нарушил контрактные обязательства. Другим претендентом стал представитель Белоруссии Артём Дамковский, ранее уже владевший этим титулом — поединок в итоге продлился все пять раундов, и судьи единогласно отдали победу Александру Бутенко. Выиграв титул, Бутенко провёл один рейтинговый бой, после чего в феврале 2017 года состоялась его первая защита — претендентом стал россиянин Абукар Яндиев. Очень тяжело проходил процесс сгонки веса, в итоге Бутенко провалил процедуру взвешивания, показав превышение лимита лёгкой весовой категории на пять килограммов. Тем не менее, Яндиев не стал отказывать от боя, и титульный поединок состоялся. Уже в начале первого раунда претендент предпринял агрессивную атаку, Александр не смог от неё защититься и проиграл техническим нокаутом. После поражения от Яндиева принял решение перейти в полусредний вес.
