I believe this is because contravariance. However, I am not 100% sure, because it also might be invariance.
There is an easy fix, just get rid of C generic argument:
type Fn<Arg extends string, Return extends string> = (k: Arg) => Return
interface Options<Arg extends string, Return extends string> {
  prop: Fn<Arg, Return>
}
function foo<
  Arg extends string,
  Return extends string,
>(r: Options<Arg, Return>) {
  return r
}
declare const prop: Fn<"foo", "bar">
const x = foo({ prop }) // ok
Playground
Consider this small example:
declare let stringString: Options<string, string>
declare let fooBar: Options<'foo', 'bar'>
stringString = fooBar // error
fooBar = stringString // error
As you might have noticed: stringString and fooBar are not assignable to each other.
The problem is in Arg generic type (in your example it is a). If you get rid of Arg (a), your example will compile:
type Fn<Return extends string> = () => Return
type Options<Return extends string> = {
  prop: Fn<Return>
}
function foo<
  Return extends string,
  C extends Options<Return>
>(r: C) {
  return r
}
declare const prop: Fn<"bar">
const x = foo({ prop }) // no error
It compiles, because Return is in covariant position.
Let's try to add back Arg but get rid of Return:
type Fn<Arg extends string> = (arg: Arg) => void
type Options<Arg extends string> = {
  prop: Fn<Arg>
}
function foo<
  Arg extends string,
  C extends Options<Arg>
>(r: C) {
  return r
}
declare const prop: Fn<"foo">
const x = foo({ prop }) // still error
declare let stringPrimitive: string;
declare let fooBarPrimitive: 'bar'
stringPrimitive = fooBarPrimitive // ok
fooBarPrimitive = stringPrimitive  // error
declare let stringString: Options<string>
declare let fooBar: Options<'bar'>
stringString = fooBar // error
fooBar = stringString // ok
Playground
There is still an error. Please check assignability of stringPrimitive , fooBarPrimitive, stringString and fooBar.
In first example, fooBarPrimitive literal type is assignable to string and it is expected. However, in second example, fooBar is no more assignable to stringString because of contravariance. Function arguments are in contravariant positions.
Let's try to add Return generic (in your example it is b):
type Fn<Arg extends string, Return extends string> = (arg: Arg) => Return
type Options<Arg extends string, Return extends string> = {
  prop: Fn<Arg, Return>
}
function foo<
  Arg extends string,
  Return extends string,
  C extends Options<Arg, Return>
>(r: C) {
  return r
}
declare const prop: Fn<"foo", 'bar'>
const x = foo({ prop }) // still error
declare let stringString: Options<string, string>
declare let fooBar: Options<'foo', 'bar'>
stringString = fooBar // error
fooBar = stringString // error
Playground
Please check assignability of stringString and fooBar, they are no more assignable to each other at all. In both cases you have got an error.
From what I understood, adding C generic triggers contravariant behavior of Arg generic.
This is not the first time I have faced such behavior.
Consider this example, but please turn off strictFunctionTypes flag:
type Animal = { tag: 'animal' }
type Dog = Animal & { bark: true }
type Cat = Animal & { meow: true }
declare let animal: (x: Animal) => void;
declare let dog: (x: Dog) => void;
declare let cat: (x: Cat) => void;
animal = dog; // ok without strictFunctionTypes and error with
dog = animal; // should be ok
dog = cat; // should be error
dog is assignable to animal but should not be.
Now, try add generic to animal function:
type Animal = { tag: 'animal' }
type Dog = Animal & { bark: true }
// generic is here
declare let animal: <T extends Animal>(x: T) => void;
declare let dog: (x: Dog) => void;
animal = dog; // error even without strictFunctionTypes
Now, dog is not assignable to animal even without strictFunctionTypes flag. I did not find an explanation of this behavior in docs.
See corresponding article here
Please check this answer if you are interested in *-variance topic.
P.S. I will be happy if somebody will confirm or critic my thoughts, I was trying my best