If your game is going to remain a game with just a 3D plane, you could simplify by using a quad-tree instead of an octree. However, an octree will cover all the bases, in case you decide to have things that fly, or decide not to have only a 3D plane for the ground.
An octree will almost certainly make things faster if you have 512 of those objects in existence all at one time (unless they're all very close to each other), especially if you're not batching your drawing of those objects, 512 draw calls is quite a bit for most devices. Since you've not asked, I'll assume you understand how an octree works and won't explain the details. Long story short, you should be able to check the camera frustum against the root of the octree, and then against that node's child nodes, and through recursion keep going until you reach the leaf nodes (nodes with no children of their own).
One thing to keep in mind is the size you want the smallest nodes to be. Too many subdivisions will use more memory and will result in too many frustum<->AABB checks which will end up being slower than the 512 draw calls would. For example I use a quad-tree in my engine, and in a 4096x4096 map I found that 512x512 was the optimal smallest size. This resulted, in my case, in a tree that had a depth of 4. I would recommend tweaking the minimum size until you find the sweet spot for performance.