By St. Paul himself? But if so, as in the case of Rome. He probably visited an existing church.
Probably. Spain was Rome's most important colony, and even aside from influence of the large Roman military presence (where many of the original Spanish Christians came from), it was in contact with the important currents of thought and behavior found in Rome at the time. And then there is the tradition that Santiago (St. James) evangelized Spain, although virtually all scholars discount this. Still, you never know...