I think that Boris is Syldavian by birth. It would be to difficult to reach the senior position of aide-de-camp to a King if he was a foreigner. It's not unheard of but not very common.
Hmmm... I think you are making some very large assumptions, to be honest, and without a series of examples one way or the other, it's hard to say for certain how common anything was.
Syldavia and Borduria may have been very closely tied until not long before the events of Sceptre
(recalling how Belgium itself was a very recently formed country). If there had been some relatively recent split, it might help explain why the Z.Z.R.K. was so keen to change things.
There may also be some sort of history of nobility moving freely - "British" aristocracy actually isn't a cohesive thing, but a collection of separate orders of nobility linked to the home nations of the United Kingdom and Northern Ireland, plus those titles which were held in Ireland prior to partition. So although the state of Eire has no nobility and confers no peerages, etc., those titles which existed prior to the separation are still held and recognized as valid in Britain.
Boris may have been of an aristocratic class that existed between Borduria and Syldavia in a similar way.
The fact that Kaiser Willhem II was a Field Marshal of the British Army (because his granny was Queen Victoria), until WWI led to his rank being stripped, and Hitler's rise to be Chancellor of Germany, even though he was an Austrian, shows the sorts of complications that abounded back in the days when European borders changed regularly, and royalty and aristocracy were shared by many countries.
Hitler and his ilk saw themselves as part of a greater state which was not bound by the borders that history had left them with, and I think that Boris is meant to be much the same.
I should think that Miller is a native of that nation; there is no indication that he is not.
Equally there is nothing which shows he is
. We simply don't know.