Funny that no one actually gave a type that would work. Here's one such:
def foo(x: Int): String = x.toString
def bar(x: Boolean): String = x.toString
val m = Map[String, (Nothing) => String]("hello" -> foo, "goodbye" -> bar)
The reason why it works this way is because Function1 is contra-variant on the input, so (Nothing) => String is a superclass of (Int) => String. It is also co-variant on the output, so (Nothing) => Any would be a superclass to any other Function1.
Of course, you can't use it like that. Without manifests, you can't even uncover what the original type of Function1 is. You could try something like this, though:
def f[T : Manifest](v: T) = v -> manifest[T]
val m = Map[String, ((Nothing) => String, Manifest[_])]("hello" -> f(foo), "goodbye" -> f(bar))
val IntManifest = manifest[Int]
val BooleanManifest = manifest[Boolean]
val StringManifest = manifest[String]
m("hello")._2.typeArguments match {
case List(IntManifest, StringManifest) =>
m("hello")._1.asInstanceOf[(Int) => String](5)
case List(BooleanManifest, StringManifest) =>
m("hello")._1.asInstanceOf[(Boolean) => String](true)
case _ => "Unknown function type"
}