I feel like I could write a ton on the subject of digital vs traditional and what makes a piece seem "Too Digital". But I would probably go whizzing by any practical advice and tread more in the theoretical or philosophical aspects of digital vs traditional.
Really, some quality digital brushes will get you part of the way there, but I think at the end of the day its your understanding of the traditional medium you're looking to emulate even slightly, along with your knowledge of the basics of painting that will get you the closest to achieving that more traditional look with digital tools. Have you done any art using traditional mediums like Watercolors or Oils?
So to the question at hand; I wouldn't say this looks too digital, just that it looks about as digital as most digital art. I think certainly some brushes could help give you some textures that you're looking for, and while I've been painting with Photoshop since around 2000 I've only just started trying pro-create and I think it's pretty damn cool and can definitely help give you some of that traditional flair your after. 
But I would suggest doing art in say Watercolor if you haven't, and letting that medium force you to learn about it by way of using it. Some of the best digital artists that I've seen who's digital work doesn't have that "digital" feel have seemingly either started as traditional artists, or have fully embraced digital art as it's own medium and haven't attempted to try and make it look traditional, if that makes sense. 
I can't help but think the main thing to focus on above brushes or trying to get it to look like a type of traditional medium is to just keep focusing on the basics such as drawing, composition, design, values and understanding color. All things that you could spend a life time trying to grasp I know, Haha. But honestly I think those who seem to best avoid that "Too Digital" look are often the ones who understand all those other aspects. And you'll find they can apply them to whatever medium digital or traditional they chose.
OH, and I think I like the first one more, I know the yellow helps break the Anemone away from the clown fish, but I still like the orange. I would suggest maybe adding slight variations of that orange in each of the anemone's tentacles and see how that looks. Not drastically different, but enough to kind of give it some noise so to speak.
