Scala, 234 226 234 bytes

def f=scala.io.StdIn.readLine.split(" ");val a=f;val b=f;val c=f;val h=for(d<-a;e<-("" +: b);g<-c;if(d.head.toLower==g.head&&(e.isEmpty||e.head==g.head))) yield s"$d's $e $g".replace("  ", " ");scala.util.Random.shuffle(h.toList).head

(A try it online link would be here but I couldn't find any online Scala runners that accepted StdIn. Try it on your computer!)

Ungolfed:

def splitInputLine = scala.io.StdIn.readLine.split(" ")

// Since names is only evaluated once, it doesn't look like it needs to be a val,
// but it needs to be evaluated before all the others.
val names = splitInputLine
val adjectives = splitInputLine
val nouns = splitInputLine

val allPossible = for {
  name <- splitInputLine
  adjective <- ("" +: adjectives) // Add the choice of no adjective
  noun <- nouns
  if(name.head.toLower == noun.head && (adjective.isEmpty || adjective.head == noun.head)) // Filter out so only matching entries remain
} yield s"$name's $adjective $noun".replace("  ", " ") // Get rid of artifact created by the empty adjective selection

scala.util.Random.shuffle(allPossible.toList).head // Get a random element

Scala, 234 226 234 206 bytes

-28 due to the fact I thought it had to accept StdIn, it's a function now

def f(a:List[String],b:List[String],c:List[String])=scala.util.Random.shuffle(for(d<-a;e<-("" +: b);g<-c;if(d.head.toLower==g.head&&(e.isEmpty||e.head==g.head))) yield s"$d's $e $g".replace("  ", " ")).head

Try it online!

Ungolfed:

def f(names: List[String], adjectives: List[String], nouns: List[String]) = {
  val allPossible = for {
    name <- names
    adjective <- ("" +: adjectives) // Add the choice of no adjective
    noun <- nouns
    if (name.head.toLower == noun.head && (adjective.isEmpty || adjective.head == noun.head)) // Filter out so only matching entries remain
  } yield
    s"$name's $adjective $noun"
      .replace("  ", " ") // Get rid of artifact created by the empty adjective selection

  scala.util.Random.shuffle(allPossible.toList).head // Get a random element
}

Scala, 234 226 bytes

def f=scala.io.StdIn.readLine.split(" ");val b=f;val c=f;val h=for(d<-f;e<-("" +: b);g<-c;if(d.head.toLower==g.head&&(e.isEmpty||e.head==g.head))) yield s"$d's $e $g".replace("  ", " ");scala.util.Random.shuffle(h.toList).head

(A try it online link would be here but I couldn't find any online Scala runners that accepted StdIn. Try it on your computer!)

Ungolfed:

def splitInputLine = scala.io.StdIn.readLine.split(" ")

// val names = splitInputLine // Since names is only evaluated once, no need to make it a val
val adjectives = splitInputLine
val nouns = splitInputLine

val allPossible = for {
  name <- splitInputLine
  adjective <- ("" +: adjectives) // Add the choice of no adjective
  noun <- nouns
  if(name.head.toLower == noun.head && (adjective.isEmpty || adjective.head == noun.head)) // Filter out so only matching entries remain
} yield s"$name's $adjective $noun".replace("  ", " ") // Get rid of artifact created by the empty adjective selection

scala.util.Random.shuffle(allPossible.toList).head // Get a random element

Scala, 234 226 234 bytes

def f=scala.io.StdIn.readLine.split(" ");val a=f;val b=f;val c=f;val h=for(d<-a;e<-("" +: b);g<-c;if(d.head.toLower==g.head&&(e.isEmpty||e.head==g.head))) yield s"$d's $e $g".replace("  ", " ");scala.util.Random.shuffle(h.toList).head

(A try it online link would be here but I couldn't find any online Scala runners that accepted StdIn. Try it on your computer!)

Ungolfed:

def splitInputLine = scala.io.StdIn.readLine.split(" ")

// Since names is only evaluated once, it doesn't look like it needs to be a val,
// but it needs to be evaluated before all the others.
val names = splitInputLine
val adjectives = splitInputLine
val nouns = splitInputLine

val allPossible = for {
  name <- splitInputLine
  adjective <- ("" +: adjectives) // Add the choice of no adjective
  noun <- nouns
  if(name.head.toLower == noun.head && (adjective.isEmpty || adjective.head == noun.head)) // Filter out so only matching entries remain
} yield s"$name's $adjective $noun".replace("  ", " ") // Get rid of artifact created by the empty adjective selection

scala.util.Random.shuffle(allPossible.toList).head // Get a random element