As i experienced the same issue, i tested all the solutions above and nothing of that solved the problem.
The only solution i found and ended that issue permanently was to :
open Settings and go for Privacy & Security
Tap Location Services and enable them if they’re not already on
go to clock and select While Using the App
Since then every watch face and every widget for sunset-sunrise works like a charm
Hope to help