Verification is a huge part of the design process; in a complex design, it would not be unusual to spend as much time, or even more time on verification than you do on the actual design. That being the case, a question which is essentially 'how do you verify complex designs' is quite broad.
In overview, if the design copes with a large number of scenarios, as indicated by there being very many states in your state machine, a good starting point for the test suite would be to have separate tests that stimulate the design so as to replicate all theses scenarios. You can then use code coverage tools to see which state transitions have been covered, and add new tests until everything is being covered. You can manage different test cases using the
configuration construct in VHDL
It might commonly be the case that there are scenarios that are variations on a theme, for example receiving a packet of some kind, but with different packet lengths, lengths that are out of bounds, etc. In these cases you can write tests that generate a number of random length packets; you would then need to make sure that all your edge cases are met, for example the minimum and maximum lengths, the minimum plus one, the maximum minus one, etc, and that your design does the correct thing in every case. You might also need to test combinations of inputs to the design, and again these combinations could be generated by a test case, as opposed to writing them out manually one by one.
There are a number of methodologies that attempt to help manage the process of generating stimulus and recording the results. I use OSVVM, which I learned about through a course a couple of years ago. I like it because it uses the same VHDL language that I am used to, along with a bit of TCL scripting, and does not require any 'extras' in order to work with my simulator. There are many alternatives, which I won't try to list here, but a quick Google search for 'fpga verification' brings up a lot of resources.