I'd recommend starting with some code that's isolated well and has a simple API. Code that doesn't rely on any platform APIs is the best candidate. For example, one of the first KMM modules I experimented with was some code that validates national identification numbers for different countries. The API was simply a function that takes a NIN string and country code and returns a boolean.
As you become more familiar with KMM, you can move from there to other parts of code that are common between both platforms, like data models and networking, utilizing available multiplatform libraries.
Things become more complicated, the closer to the UI the code gets, like platform dependencies in view models, as you pointed out. The nice thing about KMM is you can adopt it incrementally, as you build out a common shared module.