"Pan", in both Japanese and Spanish means bread. Is this purely coincidental, or do they have the same origin?
According to jisho.org パン has its origins from the Portuguese word “pão”, and was originally written as 麺麭 or 麪包 before being written as パン like it is today.
Is this pure coincidence or do they have the same origins?
Seeing as how both Spanish and Portuguese are Latin-based languages, I think it's not a stretch of the imagination to say that the origins are related.
Using the information from the comments below, I have an updated etymology for you.
1) Panis is the Latin word for bread. The Spanish pan, the Portuguese pão and French pain derive from this Latin root. (@ToddWilcox)
2) パン was introduced to Japan by Portuguese Missionaries. (see answer below, as well as this Wikipedia article compliments of @leoboiko)
This is not pure coincidence, but the Japanese did not get the word パン from Spanish, but rather Portuguese. The coincidence part is that Spanish and Portuguese are very closely related languages and share a huge volume of cognates.
It's not happenstance that things worked out this way, and I think it's interesting to understand a bit of the historical background that led to why certain words were imported as opposed to others.
First, remember a bit of interesting history of how the Catholic Church divided the entire world between Spain and Portugal. Japan fell within the domain of Protugal and I believe that the Portuguese were the first Europeans to wash up on Japan's shore during the Age of Exploration in the mid 16th century (1550's or so). The Dutch also came along shortly there after (about half a century later).
Japan had a long period of isolation following fears of what might happen if too many Christians started coming into the country: remember this was also a time of religious wars being waged between nations and forms of Protestantism and Catholic Church in Europe.
Then beginning in Meiji, the Japanese began to import many more foreign words. From German, an extensive vocabulary related to the sciences (particularly medicine); from English vocabulary related to business (and I think politics). Though, these were hardly hard and fast rules, after all, バイト <- アルバイト has its origins in the German Arbeit (though I believe that word was borrowed when both Japan and Germany were Axis nations.
Pan comes from the Portuguese word pão for wheat bread specifically and bread in general. The coincidence part is due to the fact the portuguese traders and then Jesuit and Franciscan missionaries were the first europeans to contact Japan in the 16th century. I don't have the time to confirm but I believe the portuguese had a trade monopoly with Japan for about 100 years and in that time their must have been cultural and knowledge exchange including the adoption of new vocabulary.
The most common theory is that パン originated from the Portuguese pão because Portugal traded with Japan in the 16th century. But, as somebody else already pointed out, this does not explain the パン pronunciation because pão (with a nasal sound) is closer to パウ than パン. Macao, which also traded with the Portuguese around the same time, call bread 包 (pronounced "pao"). What if パン may have actually originated from the Spanish pan, which has the exact same pronunciation? This is actually possible as the Spanish also regularly visited Japan from the Philippines. History tells us that bread was first called 波牟 (pronounced "pan" not "pamu") during the Azuchi-Momoyama period (1573-1603). This was decades after the Spanish missionary Francis Xavier visited Japan in 1549. Both Portuguese and Spanish Christian missionaries helped spread the consumption of bread through the ritual of the Eucharist, so I guess we're never going to know the correct answer to the question. Note that this was before Christianity was prohibited by Hideyoshi in 1612. (Reference: Feeding Japan: The Cultural and Political Issues of Dependency and Risk, edited by Andreas Niehaus and Tine Walravens)