I suggest upgrading the banks (places you train), to whatever level possible as this will cause more powerful Pokémon to appear and other warriors. While doing that, another suggestion is to leave some of your kingdoms unprotected (over however length of time is up to you), so someone's army will keep take over, by then, you are able to battle an army over and over again and beat them - this will give you more experience than wild battles. My final suggestion is to feed it "ponigiri" so that it stats will increase rapidly. This should at least get your Deino to 70 or 80% link.
I hope this prove's successful for you :)