Hello everyone, this is a late answer but could be useful to someone having this problems. First, you can change the folder path of your audio or videos uploaded to your server in AllVideos Plugin configuration (go to extensions and open it and change the folder paths).. then you need to CREATE these folders since they don´t exist in the system, you can do that using your cpanel file manager or if you will be working inside images/stories folder you might use Joomla Media Manager aswell.
Now, important note that may resolve your issues if everything is setup ok:
AllVideos K2 Video and Audio Player, when using local files, does not work well with file names containing spaces, accents and posibbly uppercase letters. So... for example if you are trying to upload a file named AUDIO FILE SAMPLE.mp3 change it to audio-file-sample.mp3 short names with lower casse works ok. Also do not use spaces between words, never. This should work with Image Gallery manager aswell.
Hope this helps you, my main language is Spanish so forgive my grammar mistakes. ;)