Balor was a domain of Azeroth to the west of Stormwind. It had been taken by the Horde during the First War and was held by the Stormreaver clan during the Second War. It is likely that it was liberated at the end of that war.
Balor does not appear on most recent maps and it is not currently accessible in World of Warcraft. Balor was shown on early concept maps for World of Warcraft, so it was at least in planning at one time.
Balor may not necessarily be the name of the island but the name of an outpost on an unnamed island, which might be implied by the existence of the dot on the maps of Balor. Other larger nations and regions on that map are also represented simply by dots.
With Balor's connection to the Stormreaver clan, and its location near the Tomb of Sargeras, it may be part of the Broken Isles. In that case, it would have been altered when the Tomb rose from the sea floor. If it is part of the Broken Isles, its location is now closer to the Maelstrom. However, an early WoW concept map shows that the Tomb was much further north of Balor which makes this scenario less likely.
Due to the moving of the Tomb of Sargeras out into the center of the Great Sea near the Maelstrom, it is possible that Balor (the island or the island it is located on) may have been moved as well. Its location is also similar to Hiji and/or Plunder Isle, and could have possibly been renamed when the islands of the South Seas were later fleshed out.
With the knowledge that Balor was once a domain of Azeroth, its possible that its location would have to be moved somewhere closer to the regions of the Azeroth continent in-game. One map of World of Warcraft shows some rather large islands west of the border between Stormwind City and Westfall that could possibly be candidates for Balor. Islands of that size do not show up near Westfall in-game.
The island is possibly named after Balor, the king of a race of giants (The fomorians) from Irish Mythology. Upon listening to a prophecy of his grandson killing him, Balor locked his only daughter in a tower to ensure that she may never mate.