Does anyone know how did the Balochi people, who nowadays live in South-eastern Iran and Western Pakistan, but speak North-Western Iranian languages (i.e. related to Kurdish), arrive there and what is their relation with the Kurds, except that they speak a similar language?
As you mentioned, their linguistic relation to Kurdish does imply a shared history at some time in the past. As near as I can piece together from various sources online, the split may have happened as early as 200AD though, which in terms of languages (and history) is quite a long time indeed.
They have an oral tradition of descent from Hamza, an uncle of Muhammad, and then of being chased out of Aleppo in 680 AD. However, it appears that modern linguists don't feel that jibes very well with the linguistic data, which places their origins as a culture closer to the Caspian area.
There is a historical record of them living in eastern Iran, and being driven further east to modern-day Balochistan in 972 by then Buyid Emir 'Adud Al-Dawla. Given that they have tended to be pastoralists (and occasional raiders) specializing in marginal territory, it makes sense to postulate that they slowly got pushed south-eastward from wherever they started out via similar mechanisms. But nobody really knows for sure.
The Balochis lived in Aleppo at one point, and Aleppo was ruled by the Ayyubids who were Kurds. The Ayyubids are related to the Prophet Muhammad SAW and so are the Balochis (Via Ameer Hamza). So in my opinion it's safe to say that they may have a strong bond at some point in history. The connection of the Prophet Muhammad SAW and the Ayyubids is shown in the image I added to my answer. I hope you find it useful.