Я делал так: получил украинский дупликат свидетельства - для французов признаётся равно как и советский оригинал. Получить можно либо через консульство - дофига месяцев (по-моему у меня заняло пять хотя обещали 2), либо по доверености на месте (в течении месяца наверное если учитывать получение доверености в консультсве).
На этот дупликат поставили апостиль в Минюсте в Киеве.
В Украине есть фирмы которые этим занимаются за достаточно скромные деньги - я был приятно удивлён.