Yes, you could certainly use a present perfect in the first sentence. In British English, and in more traditional variants of American English, 'just' indicates a relationship with the present time and is usually followed by a present perfect. It isn't wrong to use 'just' with past simple, however. Unlike some time phrases which require a particular tense, 'just' is something of a 'grey area'. It can be used with either a simple or a perfect aspect. As English becomes steadily more Americanised, the use of the past simple with 'just' is becoming more common. In a sentence such as the one above, I think the past simple is acceptable.

First, "Here ARE two expressions...." Just pointing it out - no judgement! English, especially American English, can be very wordy when it really doesn't need to be. Game of Thrones is another completely different situation, as the writers slip back and forth between a number of terms and dialects from English, Scottish, and other dialects. Number 1 to me indicates the guardsman really did just rode in - like he just rode by and it's nearly the present. Number 2 could have just as easily been spoken, "They captured (or "just captured") a deserter...." So like La Liseuse said, neither is more correct that they other. It appears to be more of a personal choice or literary/scriptwriter's prerogative.