When does SQL Server determine to use a new index?
when does SQL Server notice the new indexes and determines whether they actually help the query?


Immediately.  Creating an index causes a recompile because of a schema change.

Here's an illustration of this.  First to setup the objects in the test database:

use TestDatabase;
go

if exists (select 1 from sys.tables where object_id = object_id('dbo.TestTable1'))
    drop table dbo.TestTable1;
create table dbo.TestTable1
(
    Id int identity(1, 1) not null
);
go

insert into dbo.TestTable1
default values;
go 1000

if exists (select 1 from sys.procedures where object_id = object_id('dbo.GetIdFromTestTable1'))
    drop proc dbo.GetIdFromTestTable1;
go
create proc dbo.GetIdFromTestTable1
    @Id int
as
    select Id
    from dbo.TestTable1
    where Id = @Id;
go


As you would expect, running this stored procedure would result in a table scan:

exec dbo.GetIdFromTestTable1 500;
go




Now let's create an index that we know this query can benefit from:

create unique index IX_TestTable1_Id
on dbo.TestTable1 (Id);
go


Re-execute the stored procedure and take a look at the post-execution plan:

exec dbo.GetIdFromTestTable1 500;
go




We can see that our table scan turned into an index seek.  This shows that a new plan was generated.

Why?

We can trace this behavior with an XEvents session:

if exists (select 1 from sys.server_event_sessions where name = N'RecompileTracing')
    drop event session RecompileTracing
    on server;
go
create event session RecompileTracing
on server
add event sqlserver.sql_statement_recompile
(
    set
        collect_statement = 1,
        collect_object_name = 1
)
add target package0.event_file
(
    set
        filename = N'RecompileTracing.xel'
);
go

alter event session RecompileTracing
on server
state = start;
go

/*
alter event session RecompileTracing
on server
state = stop;
go

drop event session RecompileTracing
on server;
go
*/


The output we get from the above illustration/repro is that we had a sql_statement_recompile on the statement select Id from dbo.TestTable1 where Id = @Id; (condensed with removed whitespaces/tabs/newlines) and the recompile_cause is Schema changed.