Can polytheists pay Jizya?
This depends on the school of thought and on who exactly is meant by "polytheists" in your question. Mushrikeen (translated as polytheists) may include any of the following groups in Islamic nomenclature:
Apostates: It is agreed upon that Jizyah can not be accepted from apostates, no matter what their religion. This is covered elsewhere on the site. See e.g. Is punishment for leaving Islam death?
Jews, Christians and Zoroastrians: It is agreed upon that Jizya can be accepted from them. That is because 9:29 and the sunnah of the Prophet ﷺ explicitly permits it. Note that some rare dissenting opinions exist which make an exceptions for a subset of the followers of these religions, such as for the Arabs among them.
Arab idol worshipers: The view of the majority (Hanafis, Shafi'is and Hanbalis) is that Jizya is not acceptable from them. That is because there is no evidence which excludes them from 9:5 and the hadith of fighting the people until they acceptance of Islam. Further because their kufr is of a severe nature as the Prophet ﷺ lived up among them and the Quran was sent in their language and its miracle is clear to them. Further it is agreed upon is that the Prophet Muhammad ﷺ did not accept Jizya from them.
لم يختلف مسلمان في أن رسول الله - صلى الله عليه وسلم - لم يقبل من الوثنيين من العرب إلا الإسلام أو السيف
There is no difference among the Muslims that the Messenger of Allah ﷺ did not accept anything from the Arab idolators except Islam or the sword
— Al-Muhalla bi’l-Aathaar
أجمعوا على أن رسول الله - صلى الله عليه وسلم - أبى أخذ الجزية من عبدة الأوثان من العرب ولم يقبل منهم إلا الإسلام أو السيف
There is consensus that the Messenger of Allah ﷺ refused to accept Jizya from the idol worshipers from the Arabs and did not accept anything from them except Islam or the sword
— Ikhtilaf al-Fuqaha
The dominant view of the Malikis and some others is that Jizya is now acceptable from them. However it must be kept in mind that this makes little difference, as some of their scholars have noted that none of the original Arab idolators remain and all of them accepted Islam, so if one was to come across an Arab Idolator now then he would be considered an apostate and would fall under that ruling.
Other idol worshipers and religions: Jizya is acceptable from them according to the Hanafis and Malikis. That is because they have considered 9:29 and the first hadith to be general to all disbelievers and they consider it to have overruled 9:5 and similar by specification or abrogation. And some of them have argued that enslaving them is permitted, so by extension taking Jizya should also be permitted.
Jizya is not accepted from them according to the Shafi'is and Hanbalis because there is no explicit verse or hadith which excludes them from 9:5 and they hold 9:29 to be specific to only the people of the book.
Reconciling the texts:
You have mentioned being confused because of the apparent contradiction in the texts:
The Quranic verse which implies that they are to be forced to accept Islam and hence that Jizya can not be accepted from them:
فاقتلوا المشركين حيث وجدتموهم ... فإن تابوا وأقاموا الصلاة وآتوا الزكاة فخلوا سبيلهم
Kill the polytheists wherever you find them ... But if they should repent, establish prayer, and give zakah, let them [go] on their way.
— Quran 9:5
And the Hadith which seems to offer the third choice and permits taking Jizya from them:
وإذا لقيت عدوك من المشركين فادعهم إلى ثلاث خصال ... الإسلام ... الجزية ... وقاتلهم
When you meet your enemies who are polytheists, invite them to three courses of action ... Islam ... or Jizya ... or war.
These texts can be reconciled to fit either one of the madhabs.
As for those who consider it permissible to accept Jizya from the idolators, they would argue that 9:29 was revealed after 9:5 and so overrules it by abrogation or specification. And they would argue that the hadith is proof that idolators are among those from whom Jizya can be taken as the word Mushrikeen is inclusive of them.
As for those who do not consider it permissible to accept Jizya from the idolators they would argue that either the hadith is abrogated by the verse, or that it is possible that Mushrikeen is used in different senses in these two texts:
The hadith has been abrogated. That is because the verse 9:5 is from Surah at-Tawbah which was revealed after the conquest of Makkah and is among the last surah to be revealed (also see Time of the revelation of verse 9:5). While the hadith seems to be from before the conquest as it mentions migration (there was no migration after the conquest Bukhari 3077):
وإذا لقيت عدوك من المشركين ... ثم ادعهم إلى التحول من دارهم إلى دار المهاجرين
When you meet your enemies who are polytheists ... Then invite them to migrate from their lands to the land of the Muhajireen
Similarly the hadith seems to require giving invitation before fighting, and this was in the earlier period. After the dawah had sufficiently spread the Prophet ﷺ fought enemies without again offering them these terms right before the battle:
كتبت إلى نافع أسأله عن الدعاء، قبل القتال قال فكتب إلى إنما كان ذلك في أول الإسلام قد أغار رسول الله صلى الله عليه وسلم على بني المصطلق وهم غارون وأنعامهم تسقى على الماء
I wrote to Nafi' inquiring from him whether it was necessary to extend (to the disbelievers) an invitation to accept (Islam) before meeting them in fight.
He wrote (in reply) to me that it was necessary in the early days of Islam. The Messenger of Allah (ﷺ) made a raid upon Banu Mustaliq while they were unaware and their cattle were having a drink at the water
The word Mushrikeen in the hadith means disbelievers other than the idolators. Jizya is only explicitly proven from the Jews, Christians and Zoroastrians. There is no clear evidence of it being acceptable from other religions. Hence they would interpret the ruling of the hadith as follows:
When you meet your enemies who are polytheists (i.e. Christians or Zoroastrians), invite them to three courses of action.
For more detail on this see the next section of the answer.
The meaning of Mushrikeen:
While it is often translated to "polytheists", the word Mushrikeen when used in Islamic texts can mean either of the following:
- It can mean those who worship idols.
- It can mean all the disbelievers in general. In this sense it is a synonym of Kuffar. You can read more on e.g. islamqa
- It can mean a certain subset of the disbelievers. It might be used to refer to the Christians, Zoroastrians or even Jews.
As evidence for the last two consider the verse of the Quran:
وقالوا كونوا هودا أو نصارى تهتدوا قل بل ملة إبراهيم حنيفا وما كان من المشركين
They say, "Be Jews or Christians [so] you will be guided." Say, "Rather, [we follow] the religion of Abraham, inclining toward truth, and he was not of the polytheists."
— Quran 2:135
وقيل: أراد بالمشركين اليهود والنصارى
And one saying is that: Jews and Christians are meant by polytheists.
— Bahr al-Muheet
Here it can be implied that the Jews and Christians are among the Mushrikeen.
Further consider the hadith:
كان رسول الله صلى الله عليه وسلم يصوم يوم السبت ويوم الأحد أكثر ما يصوم من الأيام ويقول: إنهما يوما عيد للمشركين فأنا أحب أن أخالفهم
The Messenger of Allah used to fast on Saturdays and Sundays more than on other days, and he used to say, "They are days of festival for the polytheists, and I like to act contrary to them."
— Mishkat al-Masabih
السبت لليهود والأحد للنصارى
Saturday for the Jews and Sunday for the Christians
— Mirqaat al-Mafaateeh Sharh Mishkaat al-Masaabeeh
Mushrikeen is used here to mean the Jews and Christians, since they are the ones who celebrate Saturday and Sunday.
Further consider the hadith:
خالفوا المشركين، وفروا اللحى، وأحفوا الشوارب
Do the opposite of what the polytheists do. Keep the beards and cut the mustaches short.
قوله خالفوا المشركين في حديث أبي هريرة عند مسلم خالفوا المجوس وهو المراد في حديث بن عمر فإنهم كانوا يقصون لحاهم ومنهم من كان يحلقها
Ibn Umar's hadith is "Do the opposite of what the polytheists do." And the hadith of Abu Hurairah in Sahih Muslim is "Do the opposite of what the Zoroastrians do", and the ones meant [by 'polytheists'] in the hadith of Ibn Umar are also the Zoroastrians since they are the ones who used to trim or shave their beards.
— Fath al-Bari
In this hadith Mushrikeen means the Zoroastrians, since they are who had the custom of growing their mustache and trimming their beards. This is also supported by the version of Sahih Muslim which says "خالفوا المجوس i.e. do the opposite of the Zoroastrians".
Further consider the hadith:
قال رسول الله صلى الله عليه وسلم يوم قريظة لحسان بن ثابت: اهج المشركين، فإن جبريل معك
On the day of Quraiza's (siege), Allah's Messenger (ﷺ) said to Hassan bin Thabit, "Satirize the polytheists (with your poems), and Jibril is with you."
It seems that here the Banu Quraiza are labelled as Mushrikeen, and it is known that they were Jews.