Is it not possible to use a template in the title for the map card?

I would not suggest placing a Map card into config-template-card (CTC).
To update itself when an entity changes (like “moved to another location”), the CTC card needs to have this entity declared as “monitored”:

type: custom:config-template-card
entities: # monitored entities
  - device_tracker.xxx
card:
  type: map
  title: ${...some JS template...}
  entities:
    - device_tracker.xxx

But then the CTC will redraw the whole Map on every update - i.e. you can set a needed zoom or focus a needed marker - and suddenly on a next update everything is reset to default.
To avoid this redraw:

  1. Either DO NOT declare this entity as “monitored” - but since at least ONE entity must be set as “monitored”, use any entity which is not changed frequently:
type: custom:config-template-card
entities:
  - input_text.some_test_helper
card:
  type: map
  title: ${...some JS template...}
  entities:
    - device_tracker.xxx

But then you will not see an updated map every time the entity is changed, you will need to refresh manually (F5).
2. OR - place the Map card into a custom auto-entities card - search in the main auto-entities thread for my example for Gauge card.

But in fact this whole thing may be avoided if you place a stock Markdown card (which supports jinja) along with a Map card into a custom stack-in-card which allows to stack cards seamlessly:

type: custom:stack-in-card
... set needed settings, check docs for stack-in-card
cards:
  - type: markdown
    content: ... place jinja template
  - type: map
    ....

Here the Markdown card will play a role of your title; you will need to style a font-size etc to make it looking like a title.