A group of raters (about 20) will be watching a series of videos and will be classifying them into 4 categories. I will be running a Fleiss' kappa to measure the agreement. How does one compute for the sample size to arrive at 0.8 power, 0.05 alpha? Also, will that sample size be the number of videos to be evaluated?
The paper by Cantor available here and entitled sample size calculations for Cohen's kappa may be a useful starting point. It seems to be widely available on the web if that link fails. But note @Jeremy has wisely pointed out in a comment that the hypothesis that $\kappa = 0$ is rarely of interest.
I am not sure you can relate the power and the significance level with the Fleiss' kappa but:
I have demonstrated the sample size based on several values of p and q, the probabilities needed to calculate kappa (for the case of several categories), making scenarios by amount of classification errors made by the appraisals.
Yes, the sample size you'll obtain will be the number of videos to be evaluated.