Your question is "As far as I know, Past Perfect comes along with Past Simple, but can it be used together with Present Perfect?". The answer depends on where they appear in the sentence.
You have changed "she knew that" from simple perfect to simple present "she knows that". In its new form, it no longer makes any difference to the tenses, as the situation now is the situation that she knows.
The key event in the past is the battle. Looking at the possibilities that you suggested, plus a couple of others, for parts A and B of the rest of the sentence, we have:
A1) many of the men who had followed him into that battle
past perfect simple - valid because it was a completed action before the battle
A2) many of the men who have followed him into that battle
present perfect simple - not valid because it is no longer in force
A3) many of the men who followed him into that battle
past simple - valid because it's still a completed action.
B1) [the men] have never marched back
present perfect simple - valid because it started in the past and continues into the present
B2) [the men] had never marched back
past perfect simple - not valid because it wasn't a completed action before the battle
B3) [the men] never marched back
past simple - valid because, if they were going to come back, they would have done it long before now, so not having done it is a completed action.
B4) [the men] did not march back
past simple - valid (see B3).
You have several choices, then:
A1 works with B1 and B3 (B2 is out anyway and B4 doesn't sound right)
A2 is out, as explained above
A3 works with B1, B3 and B4