To start with, your Map[String,String] is already a Seq[(String,String)], you can formalise this a bit by calling toSeq if you wish:
val xs = Map("UK" -> "London", "France" -> "Paris")
xs.toSeq
// yields a Seq[(String, String)]
So the problem then boils down to finding countries that aren't in the map. You have two ways of getting a collection of those countries that are represented.
The keys method will return an Iterator[String], whilst keySet will return a Set[String]. Let's favour the latter:
val countriesWithCapitals = xs.keySet
val allCountries = List("France", "UK", "Italy")
val countriesWithoutCapitals = allCountries.toSet -- countriesWithCapitals
//yields Set("Italy")
Convert that into an error in whatever way you see fit.