The Octopets clams are very good to start out with but they are very small and your octopus will soon outgrow them.
The shrimp would be good, but will take some months for them to get large enough to use as feed. It would be a good project for you.
Don't bother with the brine shrimp.
Your best bet is to order fiddler crabs from the Aquaculture Store, use these together with good quality frozen ocean shrimp. It's easy to set up a little bowl for the fiddlers to keep them short term.
Yeah i will most likely get the fiddlers because i already have a small tank set up i could put them in. Arent they a little big for my octo now? I just saw him as a whole tonight and hes rather small.
Yes, small hermit crabs, maybe even a few smaller snails, would be good octo food right now. Many LFSs carry small hermits, but they're cheaper online, if you can work out the shipping.
Also, if you phone the Aquaculture Store, you can ask whether they have small fiddler crabs. I've received some only a 1/2 inch across from them on request, but it depends on what they have. But do get some live food for your little octo soon.