Does the 'FFTW' have a cost of k*N*log_2(N)?
You are trying to describe a complex phenomenon with a simple formula. That gets you only a rough approximation or an estimate but depending how much accuracy you need, you will have to dive deeper into the specifics. A few points


Any actual operation count will depend heavily on the hardware: Instruction set, pipeline, memory architecture, cache strategies, hardware accelerators, etc. In many cases the choice of the "best" algorithm is actually hardware dependent. Your best shot here is benchmarking and profiling on the target hardware.
The good old N/2*log2(N) formula basically describes the "number of butterfly operation" in a standard Cooley Tuckey FFT. So a 32-point FFT has 16*5 = 80 butterfly operations. There are 5 stages of 16 butterflies each. This is typically (but not always) the bulk of the work so it's a decent estimate for the overall complexity.
One butterfly has one complex multiply and two complex adds (or on
add and one subtract if you are picky about). The number of operations required will depend widely on the Hardware. An Analog Devices Sharc SIMD processor can do this with about 3 operations, an general purpose processor might take up to 20 operations.
There is a lot of other stuff that isn't part of the butterflies: bit-reversing, looping &amp; branching, coefficient calculation storage and retrieval. These can factor heavily into your MIPS count as well and are even more hardware dependent.
The first two stages (for decimation in time) use only simple coefficients like +1, -1, +j, -j and don't need a full complex multiply. Most algorithms take advantage of this and so the first 2*log2(N) butterflies are a little cheaper. By how much depends again on the hardware.
Non power of two FFTs get more complicated. Let's look at a 96 point FFT. First you need 3 FFTs of 32 points each, so that is 3*5*16 = 240 butterflies. Then you need to assemble the result which takes 2 complex multiplies and 2 complex adds per sample, so it's another 96*2=192 extra complex multiplies and 192 complex adds. Total would be 432 mpy and 672 adds. A 128 FFT would have 448 mpy and 896 adds, so it may be better just to zero pad and use the larger power-of-two FFT as it greatly simplifies coefficient calculation and storage.
The more prime factors you have in the FFT length the more complicated and less efficient the algorithm gets. 
In your specific case, I'd zero pad the 1920 to 2048 (unless you need true circular convolution, which I don't believe you do here). It's highly unlikely that any prime factorization (128*3*5) would do better. The 1080 is awkward, since it's just a tad over 1024. I'd probably zero pad to 1280 and do a 256*5 or zero pad to 1152 and do 128*9. You can also try the 8*27*5 and see if that's better.