For example, there is no wall separating men and women around the Kaba which is the Grand Mosque. Every where else that I know of, except for one in Denmark, has a wall separating men and women. Historically when and where did this start?
Assuming by wall you mean a gender separation, which -these days- might be found in almost all mosques around the world except al-Masjid al Haram!
There was no wall separation or any kind of separation in the Mosques in the early days of Islam. As we can find ahadith/hadiths from which we could conclude that people (men) saw women praying behind them in the mosque!
But on the other hand we know that this prayer had some rules the Messenger of Allah (peace be upon him) told us:
- Women should pray at the end or rear rows (In Sahih Muslim and here in Arabic from Musnad al-Imam Ahmad ibn Hanbal)
- Women should wait and follow the men in transitions from sujud to standing etc.. Imam an-Nawawi interpreted this hadith as a way that women don't see the 'awrah (private parts) of men (as some wore only one robe) when they stand up etc..
- Women are encouraged to leave the mosque before the men.
- The Messenger of Allah (peace be upon him) suggested a door which should only be used by women.
- On the other hand you may find ahadith which quote that it's better for a woman to pray at her home (especially the Shafi'i madhab takes this as an evidence while Maliki say it's abrogated and Hanafi also disagree as they regard the hadith as ahaad) and that woman are recommended not to go to nightly prayers ('isha) to the mosque.
But it was not possible to me to find any evidence that a separation was made neither at the early days of Islam nor until the 3rd century. But we must recall that Qur'an already quoted the hijab/veil so it was known and used (see for example (33:53)).
At least even ibn Rushd (-the grand father- 1058 a.D.-1126 a.D. or 450 a.H.-520 a.H.) in his chief work and major reference for the Maliki School al-Bayaan wa at-Tahseel البيان والتحصيل considered this as a bida'h. While al-Burzali أبو القاسم البرزلي (born 841 a.H., Arabic Wikipedia says he died 844 a.H., so one of the dates must be wrong) quoted in his encyclopedical book called Jami' masaa'il al-Ahkam mima nazala min thqadaya lilmuftynea wal Hukkam جامع مسائل الأحكام مما نزل من القضايا للمفتين والحكام (which is lists fatawa and verdicts made by earlier scholars and rulers) a Fatwa from abu al-Hassan al-Lakhmi (al-Maliki) from Qayrawan/Kairouan (died 478 a.H.) (this is my translation so read it carefully):
وللنساء عادة أنهن يصلين في الجامع، وفي سقائفه، ويكثر الناس يوم الجمعة، فربما اتصلت صفوف الرجال بالنساء، وربما خالط بعض النساء الرجال، واتفق رأي القاضي وبعض الشيوخ على أن تجعل مقصورة في بعض السقائف منه للنساء، وتثبت للسترة بالآجر، ويصلي النساء فيها في أوقات الصلاة، فقام محتسب من طلبة العلم، وقال: لا يحدث في الجامع ما لم يكن فيه قديما حتى يستشار أهل العلم ...
The woman have a tradition to pray in the mosque, and it's sheds, and on Fridays people come in great quantities, so maybe the rows of men and women get united, or maybe some women mix with men, and the judge and some scholars came together to make a box in some sheds of the mosque for women, and the veil should be fixed by bricks, so that women can pray their at the prayer times. Then one who is counted among the students of knowledge said: nobody should do (change) in a mosque something which has not being done in the early days without consulting people of knowledge ...
فأجاب - أبوالحسن اللخمي رحمه الله - ... وإذا كان الموضع الذي تصلي النساء فيه للرجال إليه حاجة، ولو لم يسبقه النساء لصلى فيه الرجال لم يبن هناك شيء، ومنع النساء الإتيان، والرجال أحق به، ولو لم يضق على الرجال، ولم يحتاجوا لذلك الموضع كان بناء سترة بينهم وحاجز حسنا
And Abu al-Hassan al-Lakhmi (May Allah be merciful to him) answered ... and if the place the women used to pray in is needed by men, and even if women were not ahead of them men should pray there and nothing should be built there, and women would be prohibited to go there as men are more entitled to use it, and if it's not to small/narrow for men (if enough space is available), and they don't need the place then building a veil and separation between them would be fine
So it seems one of the first places where this started was in what we now call Tunisia at the end of the 5th Hijri Century! The verdict was based on public interest المصالح المرسلة (see What is the difference between qiyas and istislah?), note that according the definition of bida'h of imam a-Shatibi إبراهيم بن موسى الشاطبي this could harldy be considered as anything else but an innovation in the religion as he said in his al-I'tissam:
إذا وجد المقتضي وعدم المانع ومع ذلك لم يفعله النبي صلى الله عليه وسلم دل أن ذلك لا يشرع
(My own translation take it with care:
If the exigency was present and no obstacle was present, but nevertheless the Prophet Allahs prayers and blessings be upon him didn't do (change) it, this is a (clear) evidence that this matter was not ordered.
As an addition even in the Haram of Mecca (or Kaaba) women are asked to pray in the rear rows.
During Hajj or 'Umra in the early Centuries it was usual that women did tawaf by night and behind their men/husband and it's prohibited for them to mix with men and for men to mix with them during this.
(see also this fatwa in Arabic)
And Allah knows best!