This very much depends on how the labels are separated from one another in
the current document. Are they in a table, with one cell per label, like
what you get from the Tools > Envelopes and Labels wizard? If so, how many
columns are in the table, and are all the columns filled with labels or are
some columns used as spacers? If they aren't in a table, is there one blank
paragraph mark between labels, or possibly more than one, or some other
scheme?

The general idea is to make a table with exactly two columns: the labels are
all in one column (at least temporarily), and the other column is empty.
Then your macro searches the label column for text in red font color. Each
time it finds text, it makes a copy of it in the other column of the same
row. When that's complete, the macro sorts the table on the column
containing only the copy of the red text. Finally, it deletes that column,
and if necessary it reformats the table into multiple columns.

None of that can begin until we know what the original format is...