In response to (1): The Element > Set State action is entirely synchronous, AFAICT. Which is to say, if you have multiple Set State actions in series, even if they don’t depend upon each other (via "Result of [some previous step]), they complete one-after-the-other.
You can easily test this by making a workflow that does Set State for the results of a long-running search (stored somewhere as a list called “Results of long running search”), followed by Set State for some simple scalar value (e.g., set a number state to 5), followed by a Set State that sets a number custom state to “somewhere’s Results of long running search: count” (let’s call that state “Length of long running search”).
Set up a text element to that reports: (1) Results of long running search:count, (2) the number custom state set in step 2, and also (3) “Length of long running search” (the last numeric state you set in step 3).
What you’ll observe is that even though there’s no reason for Bubble to wait to populate (2), it will stay at 0 (representing the fact that it’s empty) until (1) finishes.
You can run all sorts of variations on that experiment and you’ll see that Set State actions entirely synchronous. (They are not just started in sequence – a Set State that follows another Set State will not trigger until the previous one is completed, AFICT.) This is true specifically of the Element > Set State action. Other actions can have different behavior.
In response to (2): I’m being a little didactic here, but of course a custom state that is a list is never empty (list type states do not have the property of being empty, but we can check their length via the :count property or check if their first item is not empty to establish if the list has any items.
Anyway, if you do Set State and the state you’re setting is of list type and you set it to the results of a Search, yes, the custom state’s state's:count or state's:first_item will only go high after all the item values have been fetched and the state has essentially “published” its values back to Bubble. (Of course if the Search results in a list of zero length, neither will ever go high.)