TypeScript is unable to infer type properly from a typed string variable
In order for this to work you need to make selectAnimal generic.
You might think it should be able to deal with an animal input of a union type, but the compiler isn't able to properly type check a single block of code that uses multiple expressions that depend on the same union type.  It loses track of the correlation between `${animal}s` and allAnimals.animals[animal].  The formers is of type "cats" | "dogs" and the latter is of a type like {cats: CatState[]} | {dogs: DogState[]}, and you can't generally index into the latter with the former, because "what if you've got {cats: CatState[]} and you're indexing with "dogs"?"  That can't happen, but the compiler is unable to see it.  TypeScript can't directly deal with correlated unions this way.  That's the subject of microsoft/TypeScript#30581.
If you want a single code block to work for multiple cases, the types need to be refactored to use generics instead, as described in microsoft/TypeScript#47109.  Here's how it might look for your example:
interface AnimalStateMap {
    cat: CatState,
    dog: DogState
}

type AnimalData<K extends keyof AnimalStateMap> =
    { [P in `${K}s`]: AnimalStateMap[K][] & { allSelected: boolean } }

export interface Animals {
    animals: { [K in keyof AnimalStateMap]: AnimalData<K> };
};
    

const selectAnimal = <K extends keyof AnimalStateMap>(
    allAnimals: Animals, animal: K, index: number) => {
    const animalPlural = `${animal}s` as const;
    // const animalPlural: `${K}s`
    const animalData: AnimalData<K> = allAnimals.animals[animal]
    animalData[animalPlural][index].selected = true;
}

The AnimalStateMap is a basic key-value type representing the underlying relationship in your data structure.  Then AnimalData<K> is a mapped type that encodes as a template literal type the concatenation of s onto the type of the keys (giving such plurals as gooses and fishs 🤷‍♂️) and that the value type is of the expected animal array.  And that there's an allSelected property.
Then your Animals type explicitly written as a mapped type over keyof AnimalStateMap, which will help the compiler see the correlation when we index into it.
Finally, selectAnimal is generic in K extends keyof AnimalStateMap and the body type checks because animalPlural is of just the right generic type `${K}s` which is known to be a key of animalData, which is AnimalData<K>.
Playground link to code

I am trying to use a "freely" created string as a key for an object.
interface CatState {
    name: string,
    selected: boolean,
    color: string,
    height: number
}

interface DogState{
    name: string,
    selected: boolean,
    race: string,
    age: number,
    eyeColor: string
}

export interface Animals {
    animals: {
        cat: {
            cats: CatState[],
            allSelected: boolean,
        },
        dog: {
            dogs: DogState[],
            allSelected: boolean,
        },
    }
};

const selectAnimal = (allAnimals: Animals, animal: keyof Animals['animals'], index:number) => {
    const animalPlural = `${animal}s` as keyof Animals['animals'][typeof animal]
    allAnimals.animals[animal][animalPlural][index].selected= true
}

This highlights .selected with the message

Property 'selected' does not exist on type 'boolean'.

Here is a Playground. Is there a workaround for this, or is this simply not possible?
