Is the cipher "Kalyna" with a 512-bit key length more secure AES with a 256-bit key? Recently I have found out that Ukraine has its own symmetric encryption algorithm "Kalyna". Developers of this algorithm said that their algorithm is more secure than AES because of longer key length and lack of any vulnerabilities by hardware acceleration (like AES-NI in modern processors). Is it the truth, or is AES better?
... their algorithm is more secure rather AES because of longer key length and lack of any tables in hardware acceleration. Is it truth, or AES is better?


More key material


Using more key material does not improve security once you are already using enough key material to be secure. 


A 256-bit key is well out of the reach of mankind to crack, even if quantum computers equipped with Grover's algorithm were being used. So using more key material is not productive.

Using more key material can even weaken the security of the design, or at least make the design less efficient. 


The more bits you are working with, the longer it takes to diffuse them evenly through the rest of the state. This implies that larger keys (and larger states) need more rounds to achieve complete diffusion. 
Insufficient diffusion is one of the leading causes of weaknesses



The goal of algorithm design is basically to hit the ideal balance between efficiency and security. Due to the fact that using excessive amounts of key material will degrade performance for no benefit in security, this raises a flag regarding the competency of the design. 

That being said, if you intend to use the cipher to create a hash function, then a larger key size can be useful to compress more data per invocation of the cipher.

Lack of vulnerabilities in hardware acceleration

While it's correct that tables are a potential vulnerability in an implementation, few algorithms require the use of tables. As long as the table is a memoized function and not just an actual random permutation of words, then an implementation can always choose to evaluate the function discretely instead of using a lookup table. Note that if the table were to be an actual random permutation of words, it probably wouldn't provide good non-linearity.

Hardware acceleration is specified explicitly. The AES circuit is supported as a hardware instruction on modern Intel CPUs. It is thoroughly unlikely that this instruction will ever be replaced by Kalina Kaylna. As far as many (if not most if not all) consumers are concerned, the details of hardware accelerated Kalina Kalyna are of little concern and so are a moot point.

If you are concerned that the built-in AES circuit has deliberate vulnerabilities, you are always free to use a software implementation. While AES-NI will obviously be faster, and a softare implementation that uses tables will be fast but vulnerable to side channels, the average consumer probably does not need huge throughput anyways. So if those are a concern, you can always use an implementation that is designed to be resistant to side channel attacks.

Cryptanalysis

If you want cryptanalysis of AES, then you are free to investigate the huge amount of pre-existing research on the subject. AES has been around for years and is probably the single most heavily analyzed symmetric cipher, possibly only second to DES.

If you want cryptanalysis of Kalina, you're almost certainly out of luck. Searching for "Kalina cipher", I could not even find the proposal or definition of the design, let alone any analysis of it. Searching for "Kalina" on eprint.iacr yields no results.

Edit: With the correct spelling of the design, it is possible to locate the specification and there are a few (3) cryptanalysis results on eprint.iacr.

Because few, if any, will ever use it, it is probable that it will never receive any meaningful analysis from competent cryptographers. It is certain that it will never receive the same amount of analysis that AES has received. It is possible that some of analysis that will be performed (e.g. by NSA) will never be made public.