Q: "Invocant of method 'ASSIGN-KEY' must be an object instance" when using assignment operator Hash with typed keys…
use v6;
class Foo {}
my Hash[Foo, Foo] $MAP;

my $f1 = Foo.new;
my $f2 = Foo.new;

$MAP{$f1} = $f2;

produces the error:

Invocant of method 'ASSIGN-KEY' must be an object instance of type 'Hash[Foo,Foo]', not a type object of type 'Hash[Foo,Foo]'.  Did you forget a '.new'?

I find it misleading; what's the real error and what do I have to write instead?
I already tried the % sigil for the hash variable, that doesn't work, either.

A: In the way you have defined it, $MAP is actually a role. You need to instantiate (actually, pun) it:
class Foo {}
my Hash[Foo, Foo] $MAP;

my $map = $MAP.new;

my $f1 = Foo.new;
my $f2 = Foo.new;

$map{$f1} = $f2;
say $map;

Dead giveaway here was that classes can't be parametrized, roles do.
Also:
say $MAP.DEFINITE; # False
say $map.DEFINITE; # True

But actually the error message was pretty informative, up to and including the suggestion to use .new, as I do here.
We can shorten it down to:
class Foo {}
my %map = Hash[Foo, Foo].new ;
%map{Foo.new} = Foo.new;
%map.say;

By doing the punning from the definition, we don't need the $MAP intermediate class.

A: TL;DR JJ's answer is right, but the explanation left me confused. I currently view the problem you showed as an autovivification error/bug and/or LTA error message.
say my Any       $Any;        # (Any)
say my Hash      $Hash;       # (Hash)
say my Hash[Int] $Hash-Int;   # (Hash[Int])
$Any<a>          = 42;        # OK
$Hash<a>         = 42;        # OK
$Hash-Int.new<a> = 42;        # OK
$Hash-Int<a>     = 42;        # must be an object instance, not a type object

Imo this is a bug or pretty close to one.
A bug/problem applies for arrays too in the same scenario:
say my Any       $Any;        # (Any)
say my Array     $Array;      # (Array)
say my Array[Int] $Array-Int; # (Array[Int])
$Any[42]           = 42;      # OK
$Array[42]         = 42;      # OK
$Array-Int.new[42] = 42;      # OK
$Array-Int[42]     = 42;      # Type check failed ... expected Array[Int] but got Array

If it's best considered notabug, then perhaps the error message should be changed. While I agree with JJ that the error message is actually on point (when you understand how raku works and figure out what's going on), I think it's nevertheless an LTA error message if we don't change raku(do) to dwim.
On the gripping hand, it's not obvious to me how one could best improve the error message. And now we have this SO. (cf my point about that in Is the ... error message LTA? in a recent answer I wrote.)
Another solution

I already tried the % sigil for the hash variable, that doesn't work, either.

JJ has provided a solution that initializes with a value with an explicit .new. But that drops the constraint from the variable. To retain it:
class Foo {}
constant FooFoo = Hash[Foo:D,Foo:D];
my %foo is FooFoo;
%foo{Foo.new} = Foo.new;

Ideally the constant wouldn't be needed, and perhaps one day it won't, but I think trait parsing is limited.
