Below is a list of gentlemen who are either soundly confirmed to have explored Maine or may have based on cursory references to the area in contemporary documents.
John Cabot, or rather Giovanni Caboto, was a Venetian and is believed to have explored Maine during his second voyage to the new world in 1497 - though this is not confirmed. Like Columbus, he sailed for a sponsor nation, in this case England.
Giovanni da Verrazzano is considered to be the first European explorer of North America since the Norse expeditions, though his trip was in 1524, 27 years after John Cabots alleged visit. Verrazzano sailed on behalf of the French crown.
Don Estaban Gomez, was a Portugese cartographer. In 1524 or 1525, he explored Nova Scotia and the Maine coast and mistook the Penobscot river for the fabled Northwest Passage. According to one theory, Gomez is also responsible for naming Saco and Casco Bay.
David Ingram, an English explorer has an interesting story I'm going to have to read into more. In 1568 he was found on the coast of Nova Scotia by a French fishing vessel. Before that, his last known location was near what is today the Mexican and Texas border. According to his own accounts, he traversed the interior of North America over an 11 month period.
John Walker from England bombarded a native village in Penobscot in the year 1580.
Samuel de Champlain of France, is second to only John Smith on this list in terms of fame. He was an incredibly accomplished explorer, considered the "Father of New France" or more importantly to this blog, "The Father of Acadia." He is responsible for naming Mount Desert Island (Isles des Monts Desert) and Isle au Haut in Maine.
George Weymouth of England can partially be blamed for the lack of success at Popham Colony. In 1604 he explored the area of Monhegan and Sagadahoc and kidnapped several natives which tarnished future settler-indian relations.
Henry Hudson of England, who has all sorts of places named after him is believed to have passed through Maine in 1609 while captaining the Dutch Half Moon.
I invite readers to share with me any leads you may have regarding these explorers and their potential use of arms. I'm going to start chronologically with the two Giovannis. I'm unaware of any contemporary records of Italian arms, especially any that have been digitized, but I'm in this for the long haul.