Import all your leads into an SFMC Data Extension using an Import Interaction. Useful instructions on how to do this can be found in this Knowledge Base Article. Ensure you include your "SyncToSFMC" field in the configuration(or whatever the name of the field is in Sales Cloud).

You'll end up with a Data Extension in your Root data extension folder containing all your leads that you can now run a query on to determine leads to delete, something like this:

SELECT 
    ls.Id
FROM 
    MyImportedData i INNER JOIN 
    Lead_Salesforce ls 
        ON  i.Id = ls.Id 
WHERE
    i.SyncToSFMC = 0