What is stronger in Islam: freedom of belief (2:256) or a call to exterminate the Pagans (9:5) and jihad? Sorry, if I did somehow misunderstand or asked.
Note: I am assuming that by gentile you mean non-Muslim. In the usual sense of the word, the Prophet and the Arabs were not Israelites and hence were gentiles. And Islam is a religion and not an ethnicity or race.
The two verses apply to different circumstances.
There is no general call to exterminate non-Muslims. It only applies to arab polytheists and apostates, who when overpowered are told to accept Islam or to be executed.
The general ruling that applies to non-Muslims against whom war is fought is 9:29, they are to be fought حتى يعطوا الجزية until they agree to Jizyah, and are not to be forced to accept Islam. See the latter half of this answer for details about whom it is accepted from according to the various schools.
Anyone from whom Jizyah is accepted would become a Dhimmi and would be protected by the state and allowed to follow their religion, anyone from whom Jizyah would not be accepted would be given the choice between accepting Islam and death. Exceptions to this exist in peace treaties with non-Muslim polities9:4 and those given aman (safe conduct)9:6 .
About 2:256 Qurtubi writes:
إنما نزلت في أهل الكتاب خاصة ، وأنهم لا يكرهون على الإسلام إذا أدوا الجزية ، والذين يكرهون أهل الأوثان فلا يقبل منهم إلا الإسلام فهم الذين نزل فيهم يا أيها النبي جاهد الكفار والمنافقين . هذا قول الشعبي وقتادة والحسن والضحاك . والحجة لهذا القول ما رواه زيد بن أسلم عن أبيه قال : سمعت عمر بن الخطاب يقول لعجوز نصرانية : أسلمي أيتها العجوز تسلمي ، إن الله بعث محمدا بالحق . قالت : أنا عجوز كبيرة والموت إلي قريب! فقال عمر : اللهم اشهد ، وتلا لا إكراه في الدين
This is was specifically revealed about the People of the Book that they will not be forced to accept Islam when they pay Jizyah. The ones who will be forced are idolators, from them nothing will be accepted except Islam, and about them the verse 9:73 was revealed
This is the saying of Shabi, Qatadah, Hassan and Zahak and the evidence for this is the tradition that Zaid bin Aslam narrated from his father. He said: I heard Umar bin Khatab, he was asking an old Christian woman to accept Islam: "Accept Islam and you will be saved, verily Allah has sent Muhammad with the truth". She replied: "I am very old and close to death." On this Umar said: "O Allah! Bear witness." and then he recited: "Let there be no compulsion in religion".