When you begin play and randomly hand out the start worlds, do you shuffle the remaining start worlds into the deck?
Yes: per the Setup section of the rulebook:
Find and shuffle the five start worlds. Deal one world face up to each player. These form each player’s initial card tableau.
Shuffle the unused start worlds together with the game cards. Deal six face down cards to each player. Each player then examines these cards and discards two cards face down to the discard pile. The remaining game cards form the initial card supply.
[Bolded by me for emphasis.]