Да, всё верно. Форма местоимения всея пришла из древнерусского языка (вьсеѣ), и это форма родительного падежа женского рода. Родительный падеж среднего рода совпадает с современным: (вьсего). Таким образом, можно сказать: всея Руси, всея земли, но: всего государства.
С этих слов может начинаться официальное письмо, адресованное священнослужителю, например: Его Святейшеству, Святейшему Патриарху Московскому и всея Руси Кириллу. В словаре речь идет именно о таком употреблении.
Неофициально Вы продублировали официальный титул. Он, как правило, сокращается: прошла встреча папы и патриарха.
Да, в этом случае следует использовать обращение Ваше Святейшество.
При официальном титуловании правильно: Патриарх Московский и всея Руси. Вне такого употребления слово патриарх пишется со строчной, например: патриарх Кирилл, прием у патриарха.
Не в официальных текстах верно написание со строчной буквы: патриарх.
