addChild.fs

let addChild updateNode addNode value parent =
  match withNewChild value parent with
  | None -> async.Return None
  | Some (newParent, child) as path ->
    async { do! addNode child
            do! updateNode newParent
            return Some child }
            
let addChildById getNode updateNode addNode logAction value parentId =
  async { let! parent = getNode parentId
          let! childOpt = addChild updateNode addNode value parent
          match childOpt with
          | None -> return None
          | Some child -> 
            let action = AddNode { value = value; nodeId = nodeId; leafId = child.id }
            do! logAction action 
            return Some child.id }

First, I would split the Db functions into their own module instead of passing them as parameters.

module Db =
    let getNode context id = ...
    let updateNode context node = ...
    let addNode context node = ...

Then I would get rid of all other concerns when sequencing your writes. Also, not quite sure what conditions are present for withNewChild to return None... maybe when parent is None? In that case, you can have one option check at the top instead of embedding them throughout your code.

module Write =
    let addChild context value parent =
        async {
            let (newParent, child) = withNewChild value parent // parent not Option
            do! Db.addNode context child // assuming child is mutated to set ID
            do! Db.updateNode context newParent // assuming newParent mutated to set ID
            return (newParent.id, child.id)
        }

    let addChildById log context value parentId =
        async {
            let! parentOpt = Db.getNode context parentId
            match parentOpt with
            | None -> return None
            | Some parent ->
                let! (parentId, childId) = addChild context value parent
                do! log <| AddNode { value = value; nodeId = parentId; leafId = childId }
                return Some childId
        }