How to model small details above curved surfaces?
If what you want to do allows it (several kinds of shoes in the question, but maybe this is ok for second and third pictures), you can obtain this very simply:

The model is a simple cube opened at its base, with a vertex group that is one for the bottom vertices and 0 for the top.

Modifiers:

Subdivision that will propagate smoothly the vertex group values and gives geometry for the shrinkwrap below
Shrinkwrap to project on the surface, using the vertex group
Bevel... to bevel and smooth the base


This is not a pure modeling, surely... but its quick and often invisible for small details.