«Русский орфографический словарь» РАН фиксирует: Баба-яга (сказочный персонаж) и баба-яга (безобразная злая старуха).

Слово персонаж в единственном числе склоняется как неодушевленное существительное (ввести комический персонаж). Во множественном числе закономерность такая: при употреблении в знач. «действующие лица» это слово ведет себя как неодушевленное существительное (т. е. винительный падеж совпадает с именительным: ввести новые персонажи), но в знач. «люди» персонаж употребляется как одушевленное существительное (т. е. винительный падеж совпадает с родительным: Чичиков напоминает реальных персонажей).

Прототип – неодушевленное существительное в знач. «первоначальный образец, прообраз чего-л.»: вижу прототип нового оружия. В знач. «лицо, послужившее автору оригиналом для создания литературного образа» прототип может употребляться как одушевленное существительное.

Вижу персонажей, вижу лица людей, вижу подозрительных лиц.

Корректно склонение имени и несклонение прозвища: ходила в гости к Солеку Проклятый Меч, поссорился с Солеком Проклятый Меч. Ср.: поход Ричарда Львиное Сердце (не Ричарда Львиного Сердца), княжение Всеволода Большое Гнездо.

Трудность возникает в связи с тем, что необходимо определить: жертва – одушевленное или неодушевленное существительное? У одушевленных существительных во множественном числе винительный падеж совпадает с родительным, у неодушевленных – с именительным.

В справочнике Л. К. Граудиной, В. А. Ицковича, Л. П. Катлинской «Грамматическая правильность русской речи» указано, что у таких слов, как персонаж, существо, личность, создание, жертва и др., называющих лиц, отмечаются колебания по признаку отнесения к категории одушевленности/неодушевленности. Однако основная тенденция  здесь – употребление форм одушевленного существительного. Поэтому предпочтительно: снимали своих жертв.

По-видимому, имеется в виду Лепорелло. Это слуга Дон Жуана, ставший образом угодливого слуги, персонаж нескольких произведений, героем которых является Дон Жуан: оперы Моцарта «Дон Жуан, или Наказанный развратник» на либретто Л. да Понте, «маленькой трагедии» А. С. Пушкина «Каменный гость», драматической поэмы А. К. Толстого «Дон Жуан», одноактной пьесы в стихах Н. С. Гумилева «Дон Жуан в Египте» и др. У Мольера есть комедия «Дон Жуан, или Каменный гость», но в ней в образе слуги Дон Жуана представлен Сганарель – центральный персонаж многих комедий Мольера.

Правильно: вещий Олег.

Правильные варианты:

Мальчик с пальчик, Мальчика с пальчик и Мальчик-с-пальчик, Мальчика-с-пальчика (сказочный персонаж)
мальчик с пальчик, мальчика с пальчик и мальчик-с-пальчик, мальчика-с-пальчика (о ребенке)

Верны оба варианта, существительное персонаж может употребляться как одушевленное и как неодушевленное.

Существительное петрушка употребляется как одушевленное в значении 'кукла; театральный персонаж'. В значениях 'кукольный театр; нелепое дело' и 'растение' петрушка – неодушевленное существительное.