First, you are a bit behind on the CUs. The most recent CU is CU17, you can get it here: https://www.microsoft.com/en-us/download/details.aspx?id=56975.
Yes, it sounds like a plan-cache issue. That is, you have a bad plan in the cache, and by restarting SQL Server you clear everything out.
To prove/disprove this hypothesis, next time issue DBCC FREEPROCCACHE to clear the plan cache. If this fixes the issue, it was the plan cache. In such case, Query Store is your friend to find the culprit. (If you have not enabled Query Store, do so!)
If FREEPROCCACHE does not help, it is obviously something else. I would start with looking into the SQL Server errorlog to see what is reported there. And I would definitely slap on CU17, as it could be an issue that has been fixed.