Here's the code you can refer too :

I have assumed that your Sales Team would be Updating the title on Notes as the New Status, You will need to decide on the mechanism of Identifying Related notes with Status change and hence I have assumed you will be storing the Status in the title. Feel free to change the logic as per your requirement.

trigger leadStatusChange on Lead (before update) 
{
    leadStatusChangeHandler objHandler = new leadStatusChangeHandler();
    
    if(Trigger.isUpdate && Trigger.isBefore)
        objHandler.validateStatus(Trigger.new, Trigger.oldMap);
    
}

public with sharing  class leadStatusChangeHandler
{
    public final String strAddError = 'Please Create a Note Record';
    public leadStatusChangeHandler(){
    }
    
    public void validateStatus(List<Lead> newLeadList, Map<Id, Lead> oldLeadMap)
    {
        Map<String, String> mapLeadNotes = fetchNotes(newLeadList);
        for(Lead objLead : newLeadList)
        {
            if(oldLeadMap.get(objLead.Id).Status != objLead.Status)
            {
                if(mapLeadNotes == null || !mapLeadNotes.containsKey(objLead.Id) || !mapLeadNotes.get(objLead.Id).containsIgnoreCase(objLead.Status))
                    objLead.addError(strAddError);
            }
        }
    }
    
    public Map<String, String> fetchNotes(List<Lead> newLeadList)
    {
        Map<String, String> mapNotes = new Map<String, String>(); 
        for(Note objNote : [Select Id, Title, ParentId from Note where ParentId IN : newLeadList Order by CreatedDate DESC])
        {
            if(mapNotes != null && !mapNotes.containsKey(objNote.ParentId))
                mapNotes.put(objNote.ParentId, objNote.Title);
        }
        return mapNotes;
    }
    
}

Don't forget to mark it as 'Best Answer' if it has resolved your query.

Thanks!