Any decent provider can help provide this. Laravel is just the framework though, what is the front end application that your visitors are using? Many of our customers use Laravel so as long as the site is pretty standard, a mid size VPS or small dedicated server would be a good option for 5k UV daily.
IMHO, Hostmines.com is flexible enough to meet your specific needs. I have found them to be the best host for support, advice, and pricing out of several hosts I have ever seen before. Really nice web host!