First of all,
Estelle is gorgeous.
But, I think
Star is the sort of nickname that doesn't need a related name for it to be a nickname - it's more of a personality nickname. Like,
Margaret nn
Star, or
Sarah nn
Star, because the girls themselves feel like Stars.
Estelle nn
Star actually feels a little cutesy, because it feels more planned out ahead of time (still awesome though! I like it).
Other starry names:
Astraea, Asteria,
Nova,
Celestine.
Other names that sound starry to me but not actually star-related:
Elsa,
Odilia,
Tatiana.