Lets recount the major historical events from the earliest history of Pakistan to understand the relation of this land with various religions till it became majority Muslim.
The Indus Valley Civilization which emanated from Mehrgarh (7000 BC) in Balochistan reached its peak between 2500-1900 BC. Though the religion of these people has not been deciphered so far, it is generally assumed that they were monotheists. The fading out of this civilization was also presumed to have resulted in evolution of Rig Veda, the earliest Vedic scripture which many attribute as primarily monotheistic in nature. Indus Valley Civilization ended by 1300 BC. The Iron Age period can be taken to last roughly form 1200 to 300 BC. Most of the Vedic period (excepting the earliest phase of the core of the Rig Veda) falls within the early part of the Iron Age (12th to 6th centuries BC) and is therefore referred to by the Indians as a historical and geographical record, as no other historic records are available. However, there are various Indian Hindu religiously inclined scholars who state that Rig Veda should not be cited as historical and geographical references.
Alexander’s Indian campaign began in 326 BC in the territory of Indus by defeating Porus. Many historians relate it to the Dasarajna (Battle of ten kings) between the Purus and Bharatas as explained in Rig Veda. Those of us who have travelled on motorway M2 from Lahore to Islamabad/Rawalpindi do break journey at Bhera, a city which is over 2300 years old. This is the city which is cited as the probable location of this battle.
In 321 BC, Chandragupta Maurya founded the Mauryan Empire in India and conquered the areas under Greek rule during the Seleucid–Mauryan war (305-303 BC). The Mauryan Empire is generally said to be followers of Shiva and were probably Shaivites (monotheists). Their ruler Chandragut Maurya later converted to Jainism (monotheist). Later the ruler Ashoka became a Buddhist and it was also declared as a state religion. Mauryan Empire ruled from 322-185 BC.
Kushan Empire ruled between Ist and 3rd century BC in parts of Afghanistan and general area Taxila near Islamabad, Pakistan. The Kushans adopted elements of the Hellenistic culture of Bactria and emanated from Amu Darya area in eastern Afghanistan. Various Kushan emperors represented a wide variety of faiths including Zoroastrianism, Buddhism, and possibly Shaivism (monotheists).
The kingdom known as Kabul Shahi comprising parts of Afghanistan and Taxila ruled between 565 and 879 AD when they had Kapisa and Kabul as their capitals, and later as Hindu Shahi. The Shahis of Kabul/Kandahar are generally divided into the two eras of the so-called Buddhist-Shahis and the so-called Hindu-Shahis, with the change-over thought to have occurred sometime around 870 AD. During the 7th and 8th centuries AD the Pashtun Buddhists of the same areas also predominated the populations of Sindh and parts of Punjab as well.
When Mohammad Bin Qasim attacked Sindh in 712 AD, he was supported by Jats, Meds and Buddhists against Raja Dahir. The rulers in Sindh were high cast Brahmins who ill-treated majority population consisting of Buddhists. Thus Raja Dahir was decisively defeated. This has been mentioned in Chach Nama. The religious demography of this area is therefore clearly indicative of this fact that though in certain time periods when the rulers were Brahmin Hindus, majority population did not generally follow the religion of rulers except during the early and later Mauryan period.
From the 8th century to the 9th century AD, many inhabitants of what is present-day Afghanistan, Pakistan, and areas of northern India were converted to Sunni Islam. It is surmised from the writings of Al Biruni that around 1100 AD, some Pashtuns living in Pakhtunkhwa (present-day western Pakistan) and the neighbourhood of Sindh (ie Indus) valley had not been completely converted to Islam. Al Biruni, writing in Tarikh al Hind, also alludes to the Pashtun tribes of Pakhtunkhwa as Hindus. The word Hindu in those days alluded to the people living in a geographical location known as Al-Hind and not those who were followers of Hinduism, which was a much later characterization. In actual fact, majority of these Pashtuns were Buddhists at that time and the remaining were shaivites (monotheists). Gradually most of them came within the folds of Islam.
One aspect clearly stands out as a historical fact is that a large majority of the people living in the landmass of Indus Valley Civilization and current day Pakistan, for most part of known history since earliest times, largely followed Buddhism and Islam as their main religion and not polytheist Hinduism. And those who followed Vedic culture followed a monotheistic format instead of the later diluted polytheist culture based Hinduism.