Add lines to star with fixed coordinates maximizing smallest angle
I'll describe an efficient algorithm for this problem.

Suppose we have an angle $\theta$, and we want to find out how many new edges we can add, with the constraint that the minimum angle between all pairs of edges must be at least $\theta$.  Then it's not too hard to compute this.  Pick any adjacent pair of existing edges; suppose they are at angle $\gamma$ from each other.  Then you can add $\lfloor \gamma/\theta \rfloor - 1$ new edges between them, while ensuring the minimum angle remains at least $\theta$.  So, sort all of the existing edges by angle, iterate through each pair of adjacent existing angles, count how many new edges you can add between them (using the formula in the previous sentence), and add them up.  That tells you how many new edges you can add, if you want the minimum angle between edges to be at least $\theta$.

Great.  But in your situation, we don't know $\theta$; we just know that we want to add at least $n$ new edges.  So, use binary search on $\theta$ to find the largest $\theta$ such that you can add at least $n$ new edges while preserving a minimum angle of at least $\theta$.  You can do this by choosing a value of $\theta$, computing how many new edges you can add (using the algorithm of the previous paragraph), then increasing or decreasing $\theta$ according to the rules of binary search based on whether the number of new edges you could add was above or below $n$.