In an interrogative sentence, when the subject is a noun, a pronoun is added after the verb, pronoun gender being in accordance with that of the subject :
Paul part. ==> Paul part-il ?
Votre Majesté ne manque pas de patience. ==> Votre Majesté ne manque-t-elle pas de patience ?
In the above sentence "Votre Majesté" is the subject of the verb and the pronoun "elle" (duplication of the subject) was simply added for the correctness of the interrogative sentence.
If "Votre majesté" is used to apostrophy the king, the following is perfectly correct :
Votre Majesté, ne manquez-vous pas un peu... de patience ? Note the comma after "Majesté".
In this sentence, the first part "Votre majesté" is optional, "ne ne manquez-vous pas un peu... de patience ?" is in itself totallly correct.