Is it worth trying it on VC paper or should I try and get something graded?
By all means give it a go. There's no advantage to using graded paper for this, BTW. Graded paper is (1) barely available anymore and (2) availability is often limited to the more central grades (e.g. 2-4). If you have a very low-contrast negative, you may want to print at the highest possible contrast, which would be grade 5, which is offered by nearly every VC paper but may be impossible to find in today's market on a graded paper.
Keep in mind that exposures will be much longer than what you're used to with B&W negatives due to the orange mask.
If the darkroom print doesn't work out, you can always scan the negative and then proceed in the digital domain to make an excellent print in whatever process you like.