I don't think indexing is your (main) problem here.

There are some strange and troubling things related to timing in that execution plan. The first of which is a disparity between duration and CPU:

<QueryTimeStats CpuTime="93275" ElapsedTime="315874" />

The query ran for 5 minutes, but only used 1.5 seconds of CPU time (at DOP 1). This difference often means SQL Server is waiting on some shared resource, and not making progress running your query.

Some wait stats are captured in the execution plan:

<WaitStats>
  <Wait WaitType="RESOURCE_GOVERNOR_IDLE" WaitTimeMs="103626" WaitCount="35266" />
  <Wait WaitType="PAGELATCH_EX" WaitTimeMs="77512" WaitCount="2742411" />
  <Wait WaitType="PAGELATCH_SH" WaitTimeMs="66027" WaitCount="2037681" />
  <Wait WaitType="SOS_SCHEDULER_YIELD" WaitTimeMs="7798" WaitCount="2440" />
  <Wait WaitType="RESERVED_MEMORY_ALLOCATION_EXT" WaitTimeMs="41" WaitCount="38422" />
</WaitStats>

Resource Governor

There are over 103 seconds of RESOURCE_GOVERNOR_IDLE waits. Normally, I'd recommend that you check the server configuration and make sure that you are not being too-heavily capped as far as CPU allocation goes using a query like this:

SELECT 
    rgrp.[name],
    rgrp.min_cpu_percent,
    rgrp.max_cpu_percent, 
    rgrp.cap_cpu_percent
FROM sys.dm_resource_governor_resource_pools rgrp;

Since you are using Azure SQL Database, instead you'll need to upgrade to a tier with more compute. I noticed this in the plan XML as well:

NonParallelPlanReason="EstimatedDOPIsOne"

I think the smallest vCore options are 2, so this implies you're using one of the smallest DTU model offerings (less than S3).

Trying scaling up your database one tier at a time until you see the RESOURCE_GOVERNOR_IDLE waits reduce to a more acceptable level.

Note: this is likely contributing to the 7 seconds of SOS_SCHEDULER_YIELD as well.

Latch Waits

You also have 143 seconds of latch waits. Normally I would suspect this is some kind of tempdb contention, but there's not much evidence of tempdb usage in this query (there is one ~200 MB hash spill, and some small-ish spools).

Given the CPU cap issue, I suspect this unexpectedly high level of latch waits is related to the Azure service tier being used as well.

With the Waits

Subtracting the 246 seconds of waits discussed above, that drops the query runtime from 315 seconds to 69 seconds. It's still not amazing, but certainly better than 5 minutes. On a higher Azure service tier you may also benefit from parallel execution, further reducing the runtime.

Other approaches

If you'd prefer not to "throw hardware" at this problem, and are interested in an alternate approach, Paul White has written a very performance-conscious trigram search function and shared it here: Trigram Wildcard String Search in SQL Server

Of course this is essentially changing your whole approach, so you'll have to weigh the cost vs benefit of scrapping / rewriting what you've done so far against bumping up the Azure costs.

I don't think indexing is your (main) problem here.

There are some strange and troubling things related to timing in that execution plan. The first of which is a disparity between duration and CPU:

<QueryTimeStats CpuTime="93275" ElapsedTime="315874" />

The query ran for 5 minutes, but only used 1.5 minutes of CPU time (at DOP 1). This difference often means SQL Server is waiting on some shared resource, and not making progress running your query.

Some wait stats are captured in the execution plan:

<WaitStats>
  <Wait WaitType="RESOURCE_GOVERNOR_IDLE" WaitTimeMs="103626" WaitCount="35266" />
  <Wait WaitType="PAGELATCH_EX" WaitTimeMs="77512" WaitCount="2742411" />
  <Wait WaitType="PAGELATCH_SH" WaitTimeMs="66027" WaitCount="2037681" />
  <Wait WaitType="SOS_SCHEDULER_YIELD" WaitTimeMs="7798" WaitCount="2440" />
  <Wait WaitType="RESERVED_MEMORY_ALLOCATION_EXT" WaitTimeMs="41" WaitCount="38422" />
</WaitStats>

Resource Governor

There are over 103 seconds of RESOURCE_GOVERNOR_IDLE waits. Normally, I'd recommend that you check the server configuration and make sure that you are not being too-heavily capped as far as CPU allocation goes using a query like this:

SELECT 
    rgrp.[name],
    rgrp.min_cpu_percent,
    rgrp.max_cpu_percent, 
    rgrp.cap_cpu_percent
FROM sys.dm_resource_governor_resource_pools rgrp;

Since you are using Azure SQL Database, instead you'll need to upgrade to a tier with more compute. I noticed this in the plan XML as well:

NonParallelPlanReason="EstimatedDOPIsOne"

I think the smallest vCore options are 2, so this implies you're using one of the smallest DTU model offerings (less than S3).

Trying scaling up your database one tier at a time until you see the RESOURCE_GOVERNOR_IDLE waits reduce to a more acceptable level.

Note: this is likely contributing to the 7 seconds of SOS_SCHEDULER_YIELD as well.

Latch Waits

You also have 143 seconds of latch waits. Normally I would suspect this is some kind of tempdb contention, but there's not much evidence of tempdb usage in this query (there is one ~200 MB hash spill, and some small-ish spools).

Given the CPU cap issue, I suspect this unexpectedly high level of latch waits is related to the Azure service tier being used as well.

With the Waits

Subtracting the 246 seconds of waits discussed above, that drops the query runtime from 315 seconds to 69 seconds. It's still not amazing, but certainly better than 5 minutes. On a higher Azure service tier you may also benefit from parallel execution, further reducing the runtime.

Other approaches

A different trigram implementation

If you'd prefer not to "throw hardware" at this problem, and are interested in an alternate approach, Paul White has written a very performance-conscious trigram search function and shared it here: Trigram Wildcard String Search in SQL Server

Of course this is essentially changing your whole approach, so you'll have to weigh the cost vs benefit of scrapping / rewriting what you've done so far against bumping up the Azure costs.

Leveraging batch mode

Conor Cunningham suggested, as an experiment, to try leveraging batch mode - either using the new batch mode on rowstore, or by creating a columnstore index on the table:

...we added batch mode on rowstore in the more recent compat levels so please consider that - it will provide more benefit at higher DOPs, however. Also, a columnstore index may be an experiment to consider...