Заслуженный артист РСФСР (18.01.1990). После окончания средней школы окончил ПТУ и работал на заводе ВЭФ регулировщиком автоматической телефонной связи. Параллельно занимался в студии при художественном театре имени Я. Райниса. Впоследствии сам руководил коллективом художественной самодеятельности завода ВЭФ. Сниматься начал ещё в 17-летнем возрасте. Первая большая роль в кино – Имант Вейде в картине режиссёра Армиды Неретниеце «Клятва Гиппократа». С тех пор Буткевич снимался каждый год одновременно в нескольких фильмах. Последняя заметная работа Паула Буткевича – в телесериале «Виват, гардемарины!» С тех пор он снимается мало. Паула Буткевича куда больше любят в России, чем дома. Он играл в советских и американских фильмах, у небольших и великих режиссеров, на севере Сибири и в Индии, в комедиях провинциального уровня и международных мегапостановках.