I am from Pakistan and our Karachi consulate said to me that we need South Korea visa to visit Jeju Island, do we?
You will need a visa.
Special entry arrangements for Jeju Island is denied to nationals of the following 24 countries:
Iran, Sudan, Syria, Macedonia, Cuba, Kosovo, Palestine, Afghanistan, Iraq, Ghana, Nigeria, Yemen, Egypt, Gambia, Senegal, Bangladesh, Kyrgyz, Pakistan, Somalia, Uzbekistan, Nepal, Cameroon, Sri Lanka, Myanmar
You will need a Tourist / Transit (General) B-2-1 visa. You can apply apply here.