Does increasing k in a k-way set-associative cache always lead to a better miss rate?
It's not guaranteed; it may depend on the data. Let's say an 8-way associative cache can hold 8 items at position 512k + j for each fixed j, and a 4-way associative cache can hold 4 items at position 1024k + j. My algorithm accesses locations 1024k + 512 + j for just four values k all over again. And locations 1024k + j for lots of values k, so there is basically no cache reuse. 

In this case, 4-way associative caches has lots of hits and 8-way almost none. (There may be some mistake made somewhere, but you should figure out a pattern where 4-way ends up better).

For random access patterns, and for not carefully constructed patterns, higher associativity will be better. There is of course the problem that picking one out of 8 sets will take more time than picking one out of 2 or out of 4 sets.