At what times were people interested in prime numbers
The Liber Abaci (1202) of Fibonacci contains a chapter on perfect numbers and Mersenne primes (of course Mersenne came much later, but possibly slightly before Fermat; he is born slightly before Fermat but is essentially a contemporary).
I do not know if there are any new results; but at least it seems he was interested in them.
I am not sure if this counts as interested in prime numbers, but it is certainly number theory and involves primes very directly: the Chinses Remainder Theorem developped from about 3rd to 13th century in China (no surprise here); but also in 6th and 7th century in India.
A non-example would be the Chinese Hypothesis that used to be believed to originate in ancient China but did not.
In response to question (1), an authoritative source is Peter Rudman in "How Mathematics Happened: The First 50,000 Years". Some revelant quotes:
On the Ishango bone (20,000 BCE):
The concept of division, which must precede the concept of prime number, probably did not evolve until after 10,000 BCE and the emergence of herder-farmer cultures. The concept of prime numbers was probably only really understood after about 500 BCE by Greek mathematicians.
On the Babylonian clay tablet Plimpton 322 (1800 BCE):
This clay table shows that Babylonian scribes understood Pythagorean triples and perhaps the Pythagorean theorem. It also hints at some understandig of number concepts: prime numbers, composite numbers, regular numbers, rational numbers, and reduced fractions.
On the Sieve of Eratosthenes (250 BCE):
Is easy to apply and to understand. Babylonian scribes could have invented it more than one thousand years earlier --- but they apparently did not. Its invention was only possible after Pythagoras (500 BCE) and Euclid (300 BCE) had made the study of properties of numbers a subject worthy of the attention of Greek philosophers.
In response to question number 2, as described by O'Connor & Robertson, see also the Wikipedia entry, Islamic mathematicians were the heirs of the Greeks throughout the Middle Ages, motivated in part by their interest in practical applications of geometry and number theory to architecture and decoration. (Similarly, the Islamic law of inheritance served as a drive for the development of algebra.)
The translation by Islamic scholars of the mathematical works of Greek mathematicians was the principal route of transmission of these texts to the Middle Ages. For example, Diophantus's main work, the Arithmetica, was translated into Arabic by Qusta ibn Luqa (820–912), while the Latin translation had to wait until Xylander (1575).
Some notable Islamic heroes of prime numbers:
As noted by Stopple, the 9th century astronomer Thabit ibn Qurra studied prime numbers of the form $3\cdot 2^n-1$ (now called Thabit numbers).
Ibn Al-Haytham (born 965) seems to have been the first to attempt to classify all even perfect numbers (numbers equal to the sum of their proper divisors) as those of the form $2^{k-1}(2^k - 1)$ where $2^k - 1$ is prime. As noted by John Stillwell, Al-Haytham is also the first person that we know to state the theorem that if $p$ is prime then $1+(p-1)!$ is divisible by $p$ (only proven 750 years later by Lagrange).
Al-Farisi (born 1260) stated and attempted to prove the fundamental theorem of arithmetic, on the unique factorization of an integer into prime numbers.
Finally, the "why" question: There are no comparable heroes in Mediaeval Europe. My surmise is that this is because Christianity, with its figurative art, did not stimulate the interest in geometric and numerical patterns to the same extent as Islam did.
For 2), it depends a little on how you interpret the question. Primes in the abstract are covered in Chapter XVIII of Dickson's History of the Theory of Numbers, vol I. There's not much between Euclid and Euler.
On the other hand, primes of special forms related to perfect numbers or amicable pairs were written about extensively in the 15 centuries before Fermat. Admittedly, often incorrectly or with little content. In Chapter I of Dickson, Carolus Bovillus (1470-1553) claims that $2^n-1$ is prime if $n$ is odd, giving the example $511=2^9-1$. (In fact $7|511$). But it was not all nonsense. For example, Thabit ibn Qurra (836-901) showed that if $$ p=3\cdot 2^{k-1}-1, q=3\cdot 2^k-1, r=9\cdot 2^{2k-1}-1 $$ are all primes, then $$ m=p\cdot q\cdot 2^k, n=r\cdot 2^k $$ form an amicable pair: $s(m)=n$ and $s(n)=m$, where $s(k)$ is the sum of the proper divisors of $k$.