This is similar to Typescript: How can I make entries in an ES6 Map based on an object key/value type  and the answer here is similar to my answer there, but they are different enough that this question and answer isn't a direct duplicate.
The TypeScript typings for Map<K, V> don't reflect any more specific relationship between keys and values than "the keys are of type K and the values are of type V".  If you need something more specific, you'll need to write your own typings for it.  That involves looking at the library files and modifying them.
In your case you want each key to be an Event constructor like
type EventCtor<T extends Event> = new (...args: any) => T;
and each value to be a handler for the corresponding event like
type Handler<T extends Event> = (event: T) => void;
So we will need to write an EventToHandlerMap that behaves like some more specific version of EventToHandlerMap<EventCtor<any>, Handler<any>>:
interface EventToHandlerMap {
  forEach(callbackfn: <T extends Event>(
    value: Handler<T>, key: EventCtor<T>, map: EventToHandlerMap
  ) => void, thisArg?: any): void;
  get<T extends Event>(key: EventCtor<T>): Handler<T> | undefined;
  set<T extends Event>(key: EventCtor<T>, value: Handler<T>): this;
  readonly size: number;
}
That hopefully works how you need it; get() and set() for example are generic in T extends Event so that the key and value are related.
Then we'll need to define the Map constructor in a similar way, so that the compiler knows how to interpret the constructor arguments:
interface EventToHandlerMapConstructor {
  new <T extends Event[]>(
    entries: [...{ [I in keyof T]: [k: EventCtor<T[I]>, v: Handler<T[I]>] }]
  ): EventToHandlerMap;
  new(): EventToHandlerMap;
  readonly prototype: EventToHandlerMap;
}
const EventToHandlerMap = Map as EventToHandlerMapConstructor;
Note how I've just made EventToHandlerMap an alias of Map and asserted that it behaves as an EventToHandlerMapConstructor.  That assertion is necessary because the compiler doesn't know that Map will work that way.
Once we do that, you can use EventToHandlerMap as your constructor and get the desired behavior:
const map: EventToHandlerMap = // okay
  new EventToHandlerMap([[EventA, handleA], [EventB, handleB]]);
const map2: EventToHandlerMap =
  new EventToHandlerMap([[EventA, handleB], [EventB, handleA]]); // error
  //                              ~~~~~~~  <-------> ~~~~~~~
  // Type '(eventB: EventB) => void' is not assignable to type 'Handler<EventA>'.
  // Type '(eventA: EventA) => void' is not assignable to type 'Handler<EventB>'.
map.get(EventA)?.(new EventA("")); // okay
map.get(EventB)?.(new EventB("")); // okay
Playground link to code